PROBLEM LINK:Author: Trung Nguyen DIFFICULTY:HARD PREREQUISITES:Combinatorics, fast Fourier transform, discrete mathematics PROBLEM:You have $K$ positions. First position is breakfast for which you have to choose $L$ dishes. Any of other positions is either meal or activity. You have $A$ types of activity and $D$ dishes initially. No two meals can occur in neighbour positions. For each meal except for breakfast you choose exactly one meal. Each day new meal is added your task is to calculate number of ways to fill positions for each day and output the sum for first $T$ days. You have total of $Q$ queries of this kind, given $L$, $D$, $T$ in each query. QUICK EXPLANATION:You better read long explanation, pal. EXPLANATION:Let's calculate answer for the first day. Assume you had $t$ nonmeals activities during the day then number of ways to arrange schedule is $$\dbinom{D}{L}\sum\limits_{t=0}^{K1} \dbinom{t}{K1t}A^tD^{K1t}=\dbinom{D}{L}P_K(D)$$ Here $P_K(D)$ is polynomial of degree at most $K$. We should note that $$P_K(D)=AP_{K1}(D)+AD\cdot P_{K2}(D)$$ This recurrence will allow us to calculate this polynomial in any point using matrix exponentiation in $O(\log K)$ given that initial values are $P_1(D)=1,~P_2(D)=1+A$. Now in each query we are asked to sum up $$\sum\limits_{k=0}^{T1} \dbinom{D+k}{L} P_K(D+k)$$ To do so it would be useful to convert $P_K(D)=\sum\limits_{i} a_i D^i$ in factorial polynomial $\tilde{P}_K(D)=\sum\limits_i b_i D^{(i)}$. Where $$D^{(k)}=\prod\limits_{i=1}^{k}(D+i)$$ are rising factorials of $D$. If we do so, we can note that $$\dbinom{D+k}{L} \tilde P_k(D+k)=\sum\limits_i b_i (D+k)^{(i)}\dbinom{D+k}{L}=\sum\limits_i b_i\dfrac{(D+k+i)!}{L!(D+kL)!}=\sum\limits_i b_i L^{(i)}\dbinom{D+k+i}{L+i}$$ And given that we can rewrite the whole sum as $$\sum\limits_i b_i L^{(i)}\sum\limits_{k=0}^{T1}\dbinom{D+i+k}{L+i}$$ Now we should note that sum of binomial coefficients can be collapsed as $$\dbinom{a}{b}+\dbinom{a+1}{b}+\dots+\dbinom{a+T}{b}=\dbinom{a}{b+1}+\dbinom{a}{b}+\dbinom{a+1}{b}+\dots+\dbinom{a+T}{b}  \dbinom{a}{b+1}=$$ $$=\dbinom{a+1}{b+1}+\dbinom{a+1}{b}+\dots+\dbinom{a+T}{b}\dbinom{a}{b+1}=\dbinom{a+2}{b+1}+\dots+\dbinom{a+T}{b}\dbinom{a}{b+1}=$$ $$=\dbinom{a+T+1}{b+1}\dbinom{a}{b+1}$$ Thus the total sum we have to calculate is $$\sum\limits_{i} b_i L^{(i)}\left[\dbinom{D+i+T}{L+i+1}\dbinom{D+i}{L+i+1}\right]$$ This sum has only $O(K)$ summands which would give an answer if we know $b_i$. Let's learn to compute it. Assume we know polynomial values in $1,\dots,d$ where $d$ is degree of polynomial $P_K(D)$. Note that $$\tilde{P}(u)=\sum\limits_{i=0}^{u1}\dfrac{(u1)!}{(u1i)!}(1)^ib_i$$ If we denote $x_i=(1)^ib_i,y_i=\dfrac{1}{i!}$ then we can see that $z_i=\dfrac{P(i)}{(i1)!}$ is convolution of $x_i$ and $y_i$. But $\sum\limits_{i=0}^\infty \dfrac{x^i}{i!}=e^x$ so inverse series for it is $e^{x}=\sum\limits_{i=0}^\infty \dfrac{(x)^i}{i!}$ thus you should multiply sequence $z_i$ with first terms of $y^{1}_i=\dfrac{(1)^i}{i!}$ to recover $x_i$. This can be done on $O(K\log K)$ using fast Fourier transform. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 14 Nov, 06:26

Let $$ f_k(x) := \sum_{i=0}^k a_i x^i. $$ We would like to find the coefficients $b_0, \ldots, b_k$ of $$ f_k(x) = \sum_{i=0}^k b_i \cdot i! \binom{x+i}{i}. $$ For $n = 0, \ldots, k$, we have $$ \begin{align*} f_k(n1) &= \sum_{i=0}^k b_i \cdot i! \binom{n1+i}{i} \\ &= \sum_{i=0}^{n} b_i \cdot i! (1)^i \binom{n}{i}. \\ \end{align*} $$ By applying the binomial transform, we obtain $$ \begin{align*} b_n \cdot n! (1)^n &= \sum_{i=0}^{n} (1)^{ni} \binom{n}{i} \cdot f_k(i1), \\ b_n (1)^n &= \sum_{i=0}^n \frac{(1)^{ni}}{(ni)!} \cdot \frac{f_k(i1)}{i!}. \end{align*} $$ Lagrange interpolation can be applied using the following fact: Let $f_k(x)$ be a polynomial of degree $k$ and let $$ g(n) := \frac{\sum_{i=0}^{n} \binom{L+i}{L} \cdot f_k(i)}{\binom{L+n+1}{L+1}}. $$ Then, $g(n)$ is a polynomial of degree $k$. Proof. As explained in the editorial, $f_k(i)$ can be written using rising factorials. So, $g(n)$ can be written as follows using some constants $c_{L,0}, \ldots, c_{L,k}$: $$ \begin{align*} g(n) &= \frac{\sum_{i=0}^{n}\sum_{j=0}^{k} \binom{L+i+j}{L+j} c_{L,j}}{\binom{L+n+1}{L+1}} \\ &= \sum_{j=0}^k \frac{\binom{L+n+j+1}{L+j+1} }{\binom{L+n+1}{L+1}} \cdot c_{L,j}. \end{align*} $$ We know that $$ \begin{align*} \frac{\binom{L+n+j+1}{L+j+1}}{\binom{L+n+1}{L+1}} &= \frac{(L+n+j+1)! (L+1)! n!}{(L+j+1)! n! (L+n+1)!} \\ &= \frac{(L+1)!}{(L+j+1)!} \cdot \prod_{i=1}^{j}{(n+L+i+1)}. \end{align*} $$ Hence, $g(n)$ is a polynomial of degree $k$. answered 2 days ago

Thank's for this tutorial. It is a little bit hard to follow but mostly comprehensible.
What I do not understand is the last part related to fft beginning at "Assume we know polynomial values ...".
How can we assume to know that values. Why do we know the formula of $\tilde P(u)$?
I would also be very grateful if the section how fft is applied here to obtain $b_i$ could be explained more in detail.
Most solutions I read use Lagrange polynomials. Could someone also explain that approach?