BINOMSUM - Editorial

[melfice]

PROBLEM LINK:

Practice
Contest

Author: Trung Nguyen
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

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 non-meals activities during the day then number of ways to arrange schedule is

\dbinom{D}{L}\sum\limits_{t=0}^{K-1} \dbinom{t}{K-1-t}A^tD^{K-1-t}=\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_{K-1}(D)+AD\cdot P_{K-2}(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}^{T-1} \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+k-L)!}=\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}^{T-1}\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}^{u-1}\dfrac{(u-1)!}{(u-1-i)!}(-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)}{(i-1)!} 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.

Tester’s solution can be found here.

RELATED PROBLEMS:

[alexander86]

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?

[min_25]

@alexander86

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{aligned} f_k(-n-1) &= \sum_{i=0}^k b_i \cdot i! \binom{-n-1+i}{i} \\ &= \sum_{i=0}^{n} b_i \cdot i! (-1)^i \binom{n}{i}. \\ \end{aligned}

By applying the binomial transform, we obtain

\begin{aligned} b_n \cdot n! (-1)^n &= \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} \cdot f_k(-i-1), \\ b_n (-1)^n &= \sum_{i=0}^n \frac{(-1)^{n-i}}{(n-i)!} \cdot \frac{f_k(-i-1)}{i!}. \end{aligned}

---

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{aligned} 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{aligned}

We know that

\begin{aligned} \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{aligned}

Hence, g(n) is a polynomial of degree k.

[alexander86]

Thank you for pointing out some details!

[phben]

I didn’t know binomial transform before. Thank you!