Can someone please explain 100 marks approach in Binomial Fever problem .
Just find the polynomial for xCr (of degree r) using NTT.
Now write down the expressions for p^i , i =0 to r like a_0 + a_1*(p^i)+âĻa_r*(p^(ir)) = y_i , now sum for y_i, i =0 to N(by hand on paper) you will notice that each a_j is being multiplied with a gp.Sum that gp using the gp formula you will see that this becomes
sum a_j(p^(j*(n+1)) - 1)/(p^j-1) , j = 1 to r which is now just O(r*log(MOD))
My solution:- CodeChef: Practical coding for everyone
Also note that a_0 = 0, and you handle separately for cases p = 1, r = 1, p = MOD - 1
1 Like
can you suggest me some good resources to understand NTT .
There are two parts: First is FFT and second one is on NTT.
1 Like