You are not logged in. Please login at www.codechef.com to post your questions!

×

BINOMSUM - Editorial

2
1

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:

This question is marked "community wiki".

asked 14 Nov, 06:26

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:30

admin's gravatar image

0★admin ♦♦
16.9k347485513

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?

(2 days ago) alexander867★

@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{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$.

link

answered 2 days ago

min_25's gravatar image

7★min_25
20713
accept rate: 33%

edited 2 days ago

3

Thank you for pointing out some details!

(yesterday) alexander867★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,984
×861
×608
×247
×215
×5

question asked: 14 Nov, 06:26

question was seen: 409 times

last updated: yesterday