# Count number of the ways to fill a N-lengthed binary string

From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more than $K$.

For $N \le 2\times 10^6$, my approach is to using DP. dp[N][K] is the number of ways to fill string of length $N$ with the current $1$'s consecutive sequence length is $K$ and last parameter is to tell whether the current string contains the $1$'s consective sequence of length $K$.

This would work if N is small enough but the constraints of this problem is : $1 \le N \le 10^{10}, 0 \le K \le 50$.

The approach I need is obviously Matrix Exponentiation so I can solve it in $O(\log N \times ?)$. Storing every possible binary strings of length K is not possible ($2^M$). Can anyone provide the solution of the problem? Or at least some hints

Construct a DFA for your language (without the length $N$ restriction). It should contain $S = O(K)$ states. Consider the corresponding $S \times S$ matrix $A$, in which $A(s,t)$ is the number of characters that cause the DFA to move from state $s$ to state $t$. Let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then the number of words of length $N$ is $xA^Ny$. You can compute $A^N$ quickly using matrix exponentiation.
• I just came up with the solution of the problem. Using inclusion-exclusion, Let's find the number of way to fill the string with $1$'s consecutive sequence of length no more than $K$ and $K-1$. Then subtract the latter to eliminate the case where there is no $1$'s consecutive sequence of length $K$. By the way, thanks for your help. – PeppaPig Sep 29 '18 at 9:15