I did not actually use generating function. Only inclusion exclusion and NTT. later I eliminated NTT to get full score but for generating function you can think in this direction:
After reducing problem to this problem => Count number of ordered sequences of length “q” where each number choosen is from the set {1, 2, 3, 4. … n} and from this set first x numbers are appearing odd number of times and rest are appearing even number of times.
The answer to above problem is actually the coefficient of x^q in (1+x^2/2!+ x^4/4! …)^(n-a)* (x/1! + x^3/3! + x^5/5! …). which is further equal to coefficient of x^q in (e^x+e^-x)^(n-a) * (e^x-e^-x)^(a) (using taylor expansion). Now we have to expand this sequence using binomial expansion of only two terms.
This is my idea behind GF but I did not think further than this as some other solution came to my mind.
Always Add (+ or -) 0.10 seconds because everytime CPU time differs.
For example, you have solved a soln for 1.60 seconds, next time it can give 1.54 or 1.66 seconds for example, but the difference won’t be that high.
this part is simple for arranging the odd number of times by only row or by only column…
if i take both at same time like odd number of times row and column at same time then i got stuck with some extra cases… that part i’m not able to solve by GF… i just waste my 8 days on this problem…
by the way what is NTT ?? never heard about it…
and thanx…
NTT is “Number theoritic transform” used for fast multiplication of two polynomials where coefficients of final polynomial is required modulo some number.
There can be minor difference in time taken depending on load. You code is almost taking 2 secs.