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

Question

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][2] 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

Answer 1

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.