PROBLEM LINK:
Author: Zhuolin Yang
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
HARD
PREREQUISITES:
Fast Fourier Transform, Divide and Conquer, Lucas Theorem
PROBLEM:
Let f(n,k) be the sum of products of all size-k subsets of [n]=\{1,2,\dots,n\}. Formally
Given n\le 10^{501} and prime p\le 10^5, how many ways are there to select a k from 0 to n such that f(n,k) is not divisible by p?
QUICK EXPLANATION:
- The answer is the number of nonzero coefficients of P(x)=\prod_{i=1}^n(x+i), under modulo p;
- Let c=\lfloor n/p\rfloor, b=n\bmod p. Then P(x)\equiv f(x)g(x) \pmod p, where f(x)=[\prod_{i=1}^p(x+i)]^c and g(x)=\prod_{i=1}^b(x+i);
- You can observe the fact that \prod_{i=1}^p(x+i)\equiv (x^p-x)\pmod p;
- Let \Delta(P) be the number of nonzero coefficients of polynomial P, then \Delta(P)=\Delta(f)\Delta(g), since f has âgapâ p-1 and \deg(g) < p-1;
- \Delta(f) can be computed by Lucas Theorem; g can be computed by divide-and-conquer and FFT;
- The time complexity is the addition of two parts: converting n to p-ary which costs O(\log^2 n), and computing g which costs O(p\log^2 p).
EXPLANATION:
subtask 1
In this subtask, n\le 5000. Let f[i][j] be the product of size-j subsets of \{1,2,\dots,i\}. Then we can obtain the following dp equation:
This is because, if we choose i into our subset, the product should be i\cdot f[i-1][j-1]; otherwise it should be f[i-1][j].
We can compute f[\cdot][\cdot] in O(n^2) time and then compute the answer.
subtask 2
In this subtask, n\le 200000. We need an observation: f(n,k) is the coefficient of x^{n-k} in the polynomial
Why is that? Suppose we want to compute the coefficient of x^{n-k} of above polynomial. Think about how you multiply polynomials, and youâll realize that itâs just the sum of products over all choices of k subsets of \{1,2,\dots,n\}, which is the definition of f(n,k).
Now the task becomes to compute the product of n polynomials of the form (x+i). This can be done by divide and conquer, along with FFT. Let A(x) be the product of the first half of (x+i)'s, and B(x) be the product of rest (x+i)'s. We compute A(x) and B(x) recursively, and then compute A(x)\cdot B(x) by FFT. The time complexity is T(n)=2T(n/2)+O(n\log n), so T(n)=O(n\log^2 n). This idea is illustrated by the following pseudocode, where MUL(S) computes \prod_{s\in S}(x+s).
MUL(S)
if (|S| == 1) then return (x+s[0])
partition S into two sets S_1, S_2, each of size roughly |S|/2
A = MUL(S_1)
B = MUL(S_2)
return A*B //A*B is computed by FFT
After that, we just count the number of coefficients which canât be divided by p.
subtask 3
Following what we did before, let P(x)=(x+1)(x+2)\dots (x+n)=a_0+a_1x+a_2x^2+\dots+a_nx^n, we know that the answer is the number of a_i's which canât be divided by p. Let c=\lfloor n/p\rfloor and b=n\bmod p. Under modulo p, we have:
You can observe that(see the second last paragraph of Finite field)
Therefore
Since we only want to count the number of nonzero coefficients(after modulo p), itâs no difference if we replace (x^p-x) by (x^{p-1}-1). We let f(x)=(x^{p-1}-1)^c, and g(x)=(x+1)(x+2)\dots(x+b). For convenience, if b=p-1 we let f(x)=(x^{p-1}-1)^{c+1} and g(x)=1. Let \Delta(f) be the number of nonzero coefficients of f, then \Delta(f\cdot g)=\Delta(f)\Delta(g), since g has degree < p-1 and f has nonzero coefficients only on x^{i(p-1)} terms.
Solving \Delta(f)
Letâs suppose f(x)=(x^{p-1}-1)^k for some integer k. Then
We write k,i in base p, say k=k_1k_2\dots k_l and i=i_1i_2\dots i_l. By Lucasâs Theorem, \binom{k}{i}\not\equiv 0\pmod p if and only if \forall 1\le j\le l, i_j\le k_j. Therefore \Delta(f)=(k_1+1)(k_2+1)\dots(k_l+1) since the j-th bit of i has (k_j+1) options.
Solving \Delta(g)
\Delta(g) can be computed by the divide-and-conquer with FFT in subtask 2.
Time complexity
We need O(len^2) time to convert n into base p, where len=O(\log n) is the length of n. We need a divide-and-conquer and FFT, whose time complexity is O(p\log^2 p). Thus the total time complexity is O(len^2+p\log^2 p).
ALTERNATIVE SOLUTION:
Please feel free to share your approaches 
AUTHORâS AND TESTERâS SOLUTIONS:
Authorâs solution can be found here.
Testerâs solution can be found here.
