If this is the intended solution then I really think the time limit is unfair. I had the exact same solution but mine was taking around 6 seconds for n=2\cdot 10^6. Also, n\log^2n for n = 2\cdot 10^6 is around 8.8\cdot 10^8.
Plus the n \log n in that is from NTT/FFT which has a high constant.
Plus there is an additional n \log k for actually calculating the polynomial you want to exponentiate. I even used a faster way to exponentiate ( as discussed here ) but still TLE.
If anyone got AC using NTT/FFT then I’m definitely stealing your code.
If you like this then you might like PFRUIT and SERSUM. They also use the series expansion of e^x ( although the editorial for SERSUM doesn’t mention that approach. )
I got AC using NTT. Since K = 1 for larger test cases, so you can actually calculated e^(nx) directly, no need to do exponentiation of the polynomial as the power series of e^x was similar to the generating function.
for which problem? I didn’t expected too many WAs in ADAROOKS2 because its easy to check the conditions before submiting. I don’t know why BINARY got few ACs, I saw a similar problem in SnackDown last year, I was expecting it to be problem 3 or 4 in div2.
I am so sorry. I omitted the word BINARY
I tried a lot of solutions for this problem, and my last one was of linear time. Still I got TLE on 2 test cases. Hence the question.
ADAROOKS personally was easy for me, primarily because I used the concept of finite projective planes.
@alei basically I used the formula p^2 + p + 1 > N. Gave me all primes between 11 and 37, both inclusive, for given values of N. Then just chose my matrix based on the value of N. The approach worked solely because N started from 100 and thus the smallest matrix (100x100) has 9 rooks per row. And it only increases with N.
You didn’t answer my question though
What was the time complexity expected for BINARY?
Your solution looks very interesting. Could you explain it in a lot more detail? I looked through your code and I understand what it does but why does it work?
I would say its a coincidence because if N would have been smaller my approach would have failed. But any incidence matrix of this sort has this inherent property that the 1s do not form a rectangle and that is what we needed for this question. Since the whole matrix has this property, it wasn’t likely that its subset won’t have it as well. The only question was of satisfaction of 8N criteria, which I checked at N = 100.
.
