Pre-requisites: DP, Implementation
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.
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[i], 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 = 1.
It is quite obvious, since there is an empty string which fully satisfies to our conditions.
F = 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[i] = 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[i] 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[i].
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 = 1 for i from 1 to N do begin F[i] = 0 if ( i is a multiple of K ) begin F[i] = 1 end loop_pointer = i - 1 while ( loop_pointer is non-negative ) do begin F[i] = ( F[i] + 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[i] = 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[i] by 1.
Here is a pseudocode, which shows the implementation of the linear-time algorithm:
F = 1 G = 1 for i from 1 to N do begin F[i] = 0 if ( i is a multiple of K ) begin F[i] = 1 end F[i] = ( F[i] + G[(i - 1) modulo K] ) modulo 1000000007 G[i modulo K] = ( G[i modulo K] + F[i] ) modulo 1000000007 end
Setter’s Solution: link
Tester’s Solution: link