**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[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**that is prohibited by the constraint on

_{1}, a_{2}, …, a_{K})**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