貰う DP を考えます。\(C \ge 2\) のみ考えます。
\(dp[i] =\) (\(i\) マス目までの条件を満たす塗り方の数)
とすると、
\(i\) マス目としてありえる色の数は、\(i\) マス目の前 \(K-1\) マスが単色の場合は \(C\) 色、そうでない場合は \(2\) 色なので、
\(dp[i] = 2dp[i-1]+(C-2)(\) 前 \(K-1\) マスが単色であるような塗り方の数\()\)
です。
前 \(K-1\) マスが単色であるような塗り方は、\(i-(K-1)\) マス目を塗ってから同じ色で \(i-(K-1)+1\) マス目から \(i-1\) マス目まで塗ったものであり、その数は \(dp[i-K+1]\) です。
忘れていた \(i < K - 1\) の場合も注意すると、
\(dp[0] = C\)
\(dp[i] = 2dp[i-1]+(C-2)dp[\max(0,i-K+1)]\)
であり、計算量は \(O(N)\) です。実は \(C = 1\) の場合も上の式は成り立ちます。

実装例 : https://atcoder.jp/contests/abc279/submissions/40803392