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:
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:
And transition from P(x) to P(x-r) may be done in O(n \log n) time as well:
Where c_i are coefficients defined by some particular convolution:
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:
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:
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.