Japanese Student Championship 2019 Qualification F - Candy Retribution
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f
Before explaining the solution, we first explain the four typical problems. These often appears in various counting problems.
Problem 1
How many are there N non-negative integers such that xN = M. This is a typical question about the combinations with repetitions. The number of ways is known as H (N , M). There is a relationship between H (n , r) and C (n , r). There are M circles and N - 1 bars, then each rearrangement of them corresponds to a solution. For example, in N = 5, M = 4, (x1 , x2 , x3 , x4 , x5) = (2 , 1 , 0 , 1 , 0) corresponds to
\begin{align} \underbrace{\bigcirc \bigcirc}_{x_1} | \underbrace{ \bigcirc }_{x_2} | \underbrace{\vphantom{\bigcirc}}_{x_3} | \underbrace{\bigcirc}_{x_4} | \underbrace{\vphantom{\bigcirc}}_{x_5}. \end{align}
Problem 2
How many are there N non-negative integers such that x1 + ... + xN ≤ M. We introduce a new variable xN + 1, then we can restate the problem to x1 + ... + xN + xN + 1 = M, that is, we can restate it into the problem 1.
Problem 3
How many are there N positive integers such that x1 + ... + xN = M. By subtracting N from M, this problem is reduced to the problem 1.
Problem 4
How many are there N non-negative integers such that xN = M, xi < k. Inclusion exclusion principle. Count the ways such that the number of variables vaiolates the condition xi < k is equal to j. By subtracting jk from M, this problem is reduced to the problem 1. That is,
\begin{align} \sum_{i=0}^{N} \binom{N}{i} (-1)^i H(N,M-ki). \end{align}
Main Problem
Let us count the number of ways doesn't satisfy the condition. The condition regarding as L and R can be decomposed into f - L - 1. Integers x1 , ... , xN is sorted in descending order. We should find the number of ways that x > M + 1. We want to fix xM, but this strategy is a little difficult. So, we first find the ways of xM ≥ s, xM < t, called g (s , t), and calculate g (x , x) - g (x + 1 , x).
Let us find the number of ways of x1 , ... , xM ≥ s, M + 1 , ... , xN < t, x1 + ... + xN ≤ R. Here, we forgot the sorted condition. And then we obtain the answer by rewriting.
\begin{align} & \begin{cases} s \le x_1,\ldots,x_M \\ 0 \le x_{M+1},\ldots,x_N \lt t \\ x_1+\cdots+x_N \le R \end{cases} \\ =& \begin{cases} s \le x_1,\ldots,x_M \\ 0 \le x_{M+1},\ldots,x_N \lt t \\ 0 \le x_{N+1} \\ x_1+\cdots+x_N+x_{N+1} = R \end{cases} \\ =& \begin{cases} 0 \le x_1,\ldots,x_M \\ 0 \le x_{M+1},\ldots,x_N \lt t \\ 0 \le x_{N+1} \\ x_1+\cdots+x_N+x_{N+1} = R-Ms \end{cases} \\ =& \sum_{i=0}^{N-M} \binom{N-M}{i} (-1)^i \begin{cases} 0 \le x_1,\ldots,x_M \\ t \le x_{M+1},\ldots,x_{M+i} \\ 0 \le x_{M+i},\ldots,x_{N} \\ x_1+\cdots+x_N+x_{N+1} = R-Ms \end{cases} \\ =& \sum_{i=0}^{N-M} \binom{N-M}{i} (-1)^i \begin{cases} 0 \le x_1,\ldots,x_M \\ 0 \le x_{M+1},\ldots,x_{M+i} \\ 0 \le x_{M+i},\ldots,x_{N} \\ x_1+\cdots+x_N+x_{N+1} = R-Ms-it \end{cases}\\ =& \sum_{i=0}^{N-M} \binom{N-M}{i} (-1)^i H(N+1,R - Ms - it). \end{align}
The time complexity is O (n log n). In the analysis, we used the property that the n-th harmonic number is asymptotic to log n.
Generating Function
Let us start the explanation from the second paragraph of main problem. We can find the answer by the following way.
\begin{align}
& [x^R] (x^s+x^{s+1}+\cdots)^{M} (1+x+\cdots+x^{t-1})^{N-M} (1+x+x^2+\cdots) \\
&= [x^R] x^{sM} \frac{(1-x^t)^{N-M}}{(1-x)^{N+1}} \\
&= [x^{R-sM}] \frac{(1-x^t)^{N-M}}{(1-x)^{N+1}} \\
&= \sum_{i=0}^{\infty} [x^i] (1-x^t)^{N-M} [x^{R-sM-i}] \frac{1}{(1-x)^{N+1}} \\
&= \sum_{i=0}^{\infty} (-1)^i C(N-M,i) H(N+1,R-sM-it).
\end{align}
Here, $[x^k]$ denotes the coefficient of $x^k$. We define $[x^k] (1+x)^N = C(N,k), [x^k](1-x)^{-N}=H(N,k)$.
Formal Power Series and Prefix Sum
The opration multiplying $ 1/(1-x) $ actually means finding the prefix sum. Specifically, it transform
\begin{align}
f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots
\end{align}
into
\begin{align}
\frac{ f(x) } { 1 - x } = a_0 + (a_0 + a_1)x + (a_0+a_1+a_2) x^2 + (a_0 + a_1 + a_2 + a_3) x^3 + \cdots.
\end{align}
By this fact, we can sum over the coefficients of $1,x,x^2,\ldots,x^k$ algebraically.
Generating Functions for Problem 1 to 4.
Problem 1 $[x^M](1+x+x^2+x^3+\cdots)^{N}$
Problem 2 $[x^M](1+x+x^2+x^3+\cdots)^{N+1}$
Problem 3 $[x^M](x+x^2+x^3+\cdots)^{N}$
Problem 3 $[x^M]( 1 + x + x^2 + \cdots + x^{k - 1})^N$
It is difficult to explain why this is correct, but I think the proof of the binomial theorem is good to understand. It requires the knowledge of the combinatorial meaning of the expansion of polynomials.
Good reference of formal power series is Ivan Niven's paper "formal power series". It is written in easy words, so it is easy to read at least for me. The article in English wikipedia is also helpful. The strength of formal power series is what it accepts a lot of analytic operations. For example, consider the problem to finding the nth term of the sequence defined by the following recurrence relation.
\begin{gather}
a_0=1, a_{n+1} = \sum_{i+j+k=n} a_i a_j a_k.
\end{gather}
This problem can be solved by "Lagrange Inversion Theorem".
