BINOFEV - Editorial


Contest, div. 1
Contest, div. 2

Author: Rezwan Arefin
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

Fast Fourier transform, basics of calculus, polynomials
You have to calculate \sum\limits_{i=0}^N \binom{p^i}{r} for given N, p and r modulo m=998\,244\,353, where r \leq 10^6.
Consider P(x)=\binom{x}{r} as a polynomial of x, then you may find \sum\limits_{i=0}^N P(p^i) as:

P(p^i) = \sum\limits_{i=0}^N \sum\limits_{k=0}^n a_k (p^i)^k=\sum\limits_{k=0}^n a_k \sum\limits_{i=0}^N p^{ki}.

Note that P_r(x)=\binom{x}{r} is the polynomial of x of degree r, which coefficients may be calculated in O(r \log r). Indeed, for odd values P_r(x) are recalculated from P_{r-1}(x) and for even values of r we may rewrite it as follows:

P_{2r}(x)=\frac{x(x-1)\dots(x-2r+1)}{(2r)!} = P_r(x) \cdot P_r(x-r)

And transition from P(x) to P(x-r) may be done in O(n \log n) time as well:

P(x-r) = \sum\limits_{k=0}^n a_k (x-r)^k = \sum\limits_{k=0}^n \sum\limits_{i=0}^k a_k \binom{k}{i}x^i (-r)^{k-i}=\\ ~\\ =\sum\limits_{i=0}^n \frac{x^i}{i!}\sum\limits_{k=i}^n (a_kk! ) \cdot \frac{(-r)^{k-i}}{(k-i)!}=\sum\limits_{i=0}^n\frac{c_i x^i}{i!}

Where c_i are coefficients defined by some particular convolution:

c_i = \sum\limits_{k=i}^n (a_k k!) \cdot \frac{(-r)^{k-i}}{(k-i)!}=\sum\limits_{k=0}^{n-i} a_{k+i}(k+i)! \cdot \frac{(-r)^k}{k!}= \sum\limits_{k=0}^{n-i} \alpha_i \cdot \beta_{n-i-k}

Where \alpha_k = \frac{(-r)^k}{k!} and \beta_k = a_{n-k} (n-k)!, thus c_i is a simple convolution of \alpha and \beta. This convolution may be calculated as coefficients in the product of polynomials A(x) and B(x) having \alpha_k and \beta_k as their coefficients correspondingly.

That means that the whole time needed to calculate P_r(x) is:

T(n) = T(n/2) + O(n \log n) = O(n \log n)

Now that we know explicit coefficients of P(x)=\binom{x}{r}, our task is to calculate sum of P(p^i) for i from 0 to N for given polynomial P(x). Let it be that P(x) =a_0 + a_1x + \dots + a_n x^n, then:

\sum\limits_{i=0}^N P(p^i) = \sum\limits_{k=0}^r a_k \sum\limits_{i=0}^N p^{ik} = \sum\limits_{k=0}^r a_k \frac{1-p^{k(N+1)}}{1-p^k}

Calculating this sum will take additional O(r \log N) of time, which makes total complexity of the solution to be equal to O(r \log rN).
Author’s solution can be found here.
Tester’s solution can be found here.

EDIT: OK, it is enough to multiply everything by a constant and this is easy and calculating factorials should be easy. Still, this equation is incorrect.


is not true because (2r)! \neq (r!)^2 in general. Could you please try to fix that somehow and notify me if you do this?

Can you elaborate please? You mean that it should be \frac{(r!)^2}{(2r)!}P_r(x) P_r(x-r), right?