No K Ones in a Row — Solution & Editorial
State = current trailing run of ones (0..K−1). The transition (append 0 resets the run; append 1 extends it, forbidden at K) is a fixed K×K matrix — exponentiate it.
Complexity: O(K3 log N)
State = current trailing run of ones (0..K−1). The transition (append 0 resets the run; append 1 extends it, forbidden at K) is a fixed K×K matrix — exponentiate it.
Complexity: O(K3 log N)