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^(i*r)) = 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:- https://www.codechef.com/viewsolution/28282373

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 .

https://codeforces.com/blog/entry/43499

There are two parts: First is FFT and second one is on NTT.

1 Like