**Problem link:** contest practice

**Difficulty:** Easy-Medium

**Pre-requisites:** DP

**Problem:** Count the number of increasing sequences of **K** natural numbers, where adjacent numbers differ no more than by **D**, the first number is not greater than **D** and the total sum of all numbers in the sequence equals to **N**.

**Explanation:**

Let’s denote the original “nice” sequence by **(a _{1}, a_{2}, …, a_{K)}**. Let’s denote the sum

**a**by

_{1}+ a_{1}+ … + a_{K}**N**.

We know that

**a**. So, we can obtain a sequence

_{1}< a_{2}< … < a_{K}**(b**of natural numbers, where:

_{1}, b_{2}, …, b_{K})**b _{1}** =

**a**

_{1}**b _{i}** =

**a**-

_{i}**a**for

_{i-1}**i**in the range from 2 to

**K**.

In this new sequence **b _{i}** > 0 will be hold for every i from one to

**K**. We will call the values of

**b**

_{i}*b-values*.

Then, let’s reconstruct the sequence **(a _{1}, a_{2}, …, a_{K)}** using the sequence

**(b**. We obtain:

_{1}, b_{2}, …, b_{K})**a _{1}** =

**b**

_{1}**a _{2}** =

**b**

_{1}+ b_{2}**a _{3}** =

**b**

_{1}+ b_{2}+ b_{3}… and so on …

**a _{k}** =

**b**

_{1}+ b_{2}+ … + b_{k}Here we see that **b _{1}** occurs

**K**times in

**N**,

**b**occurs

_{2}**K-1**times in

**N**, …,

**b**occur once in

_{K}**N**.

And now, we can have a DP: **F[i][j]** corresponds to the number of ways to make the sum **i** using an increasing sequence of **j** natural numbers. The recalculation is quite simple here: when we add the **j**-th number to the sequence (having **j-1** numbers already added) we know that its’ *b-value* will occur **K-j+1** times in the final sum (in other words, in **N**). So, we can get to **(i, j)** from **(i - (K - j + 1), j - 1)**, **(i - 2 * (K - j + 1), j - 1)**, **(i - 3 * (K - j + 1), j - 1)**, … , **(i - D * (K - j + 1), j - 1)**. The value of the position **(i - D * (K - j + 1), j - 1)** is the last possible summand for the **(i, j)** DP state, because the differences larger than **D * (K - j + 1)** means larger adjacent number differences in the sequence **(a _{1}, a_{2}, …, a_{K})** that is prohibited by the constraint on

**D**.

The final time complexity is O(**N*K**). At the first glance, it’s too much for this problem. But we can check in the beginning, whether the answer is zero or not by taking the smallest possible sum of **K** natural numbers and comparing it with **N**. If this is sum is greater than **N**, we can output zero and quit immediately. Otherwise the time complexity reduces to no more than O(**N * sqrt N**) that is OK.

**Setter’s solution:** link

**Tester’s solution:** link