Clarify your ques

Go through this blog, and then try to ask your question again. https://codeforces.net/blog/entry/64993

Dp[i] — the number of ways to choose the first i elements such that they necessarily contain k consecutive same numbers. For i smaller than k the value of the dp is obviously 0. Otherwise we have two opportunities: either the last k elements are equal and the first i-k elements don't matter, or the first i-k numbers are valid(contain k consecutive same numbers). This leads us to the following transition: dp[i] = m * m ^ (i — k) + (m ^ k — m) * dp[i — k] = m ^ (i — k + 1) + (m ^ k — m) * dp[i- k]. Pre-computing the powers of m will lead to a time complexity O(n). UPD: My bad this is not true.

Here's one way to do it: let $$$f(i)$$$ be the number of ways to assign the first $$$i$$$ values subject to the constraint that no $$$K$$$ consecutive values are equal. Then $$$f(0) = 1$$$, $$$f(i < 0) = 0$$$, and $$$f(i) = (M - 1) \sum_{k = 1}^{K - 1} f(i - k)$$$.

Why? Suppose that the value of the last assigned element is $$$x \in [1, M]$$$. The number of consecutive elements with value $$$x$$$ appearing at the tail of the sequence is between $$$1$$$ and $$$K - 1$$$. Call that number $$$k$$$. The $$$(i-k)^{th}$$$ element should differ from $$$x$$$. For each assignment to the first $$$i - k$$$ values, there are $$$M - 1$$$ choices for $$$x$$$ which do not match the value assigned to the $$$(i-k)^{th}$$$ element.

So, we can find $$$f(N)$$$ in $$$O(NK)$$$ or with prefix sums in $$$O(N)$$$. The answer you want is $$$M^N - f(N)$$$.

When $$$K$$$ is small, we can also write the recurrence for $$$f$$$ as a matrix and find $$$f(N)$$$ with fast exponentiation in $$$O(K^3logN)$$$.