BINOFEV - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

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

DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Fast Fourier transform, basics of calculus, polynomials
PROBLEM:
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.
QUICK EXPLANATION:
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}.

EXPLANATION:
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 AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

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.

ORIGINAL:
But

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?

3

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

4

Yes.