**Problem Link:** contest, practice

**Difficulty:** Easy

**Pre-requisites:** DP, Implementation

**Problem:**

We need to count the number of **01**-strings of **N** chars, such that any continuous section of ones of them have a length which is a multiple of **K**.

I.e, if **K** = 2, then string **00011001111** is good, while **0011100** is not.

**Explanation:**

This problem is a dynamic programming(DP) problem. As far as it’s so, we need to think about the parameters we should use for DP.

Let’s consider the following function **F***, denoting the number of **01**-strings of **i** chars, such that any continuous section of ones of them have a length which is a multiple of **K**.

It’s a quite obvious observation, that the answer for the problem is **F[N]**.

Let’s consider some border cases.

**F[0]** = 1.

It is quite obvious, since there is an empty string which fully satisfies to our conditions.

**F[1]** = 2, in case **K** = 1, otherwise 1.

If **K** = 1, then strings **0** and **1** both satisfy to out conditions, otherwise string **1** doesn’t satisfy.

Well, it’s time to present the recurrent formula.

**F*** = **F[i - 1]** + **F[i - K - 1]** + … + **F[i - c * K - 1]** (**i - c * K - 1** is non-negative, while **i - (c + 1) * K - 1** is negative).

Also, in case **i** is a multiple of **K**, we should increase **F*** by 1.

The logic of the formula is the following:

Let’s consider the continuous section of ones, which ends in the position i. It may have a length equal to 0, **K**, **2 * K** and so on. For better understanding, let’s assume that it’s length equals to **3 * K**.

Then, all the positions from the range **[i - 3 * K + 1 … i]** are ones and **(i - 3 * k)'th** position is a zero.

We know how do the positions **[i - 3 * k … i]** look, but we don’t know what’s going on before them. That’s why we need to add summand **F[i - 3 * k - 1]** to **F***.

In case, when **i** is a multiple of **K**, we add 1, because we can’t use the logic described above.

So, here is a pseudocode, which shows the implementation of this DP:

```
F[0] = 1
for i from 1 to N do
begin
F* = 0
if ( i is a multiple of K )
begin
F* = 1
end
loop_pointer = i - 1
while ( loop_pointer is non-negative ) do
begin
F* = ( F* + F[ loop_pointer ] ) modulo 1000000007
loop_pointer = loop_pointer - K
end
end
```

Well, we have a working polynomial solution, which runs in **O(N ^ 2 / K)** time. In case **K** is a quite big number, this solution works fast, but for smaller values of **K** it’s getting TLE.

Let’s improve it!

The key observation is, that the loop for counting current **F[]** is needless.

Formally, * F = G[(i - 1) modulo K]**, where

**G[(i - 1) modulo K]**is the sum of all previous

**F[x]**, such that

**(i - x - 1)**is a multiple of

**K**.

We should maintain **G[]** while counting **F[]**. As before, in case **i** is a multiple of **K**, we should increase **F*** by 1.

Here is a pseudocode, which shows the implementation of the linear-time algorithm:

```
F[0] = 1
G[0] = 1
for i from 1 to N do
begin
F* = 0
if ( i is a multiple of K )
begin
F* = 1
end
F* = ( F* + G[(i - 1) modulo K] ) modulo 1000000007
G[i modulo K] = ( G[i modulo K] + F* ) modulo 1000000007
end
```

**Setter’s Solution:** link

**Tester’s Solution:** link