### PROBLEM LINK:

**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

Here P_K(D) is polynomial of degree at most K. We should note that

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

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

are rising factorials of D. If we do so, we can note that

And given that we can rewrite the whole sum as

Now we should note that sum of binomial coefficients can be collapsed as

Thus the total sum we have to calculate is

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

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.