### 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*[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} ot\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.