×

# BINOMSUM - Editorial

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

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:

This question is marked "community wiki".

4★melfice
811837
accept rate: 0%

19.8k350498541

3

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?

(15 Nov '17, 14:49)

 7 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(-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{align*} By applying the binomial transform, we obtain \begin{align*} 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{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 15 Nov '17, 17:20 7★min_25 262●1●3 accept rate: 66% 3 Thank you for pointing out some details! (16 Nov '17, 21:19) I didn't know binomial transform before. Thank you! (18 Nov '17, 01:51) phben6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×1,343
×891
×334
×301
×5

question asked: 14 Nov '17, 06:26

question was seen: 1,163 times

last updated: 18 Nov '17, 01:51