左から順に、同じ色で塗る連続したマスをまとめて塗ることをことを考えます。あるマスを塗ることができる色の種類数は、最も左端のマスのときC、そのマスの左側K-1マスに色が1種類のときC-1、2種類のとき1です。したがって、

\(\mathrm{dp}[c][i]=\) 長さ \(i\) で、条件を満たす塗り方で、最後の \(K-1\) マスがちょうど \(c\) 色になる方法の数
として、最も右のマスと同じ色を何マス連続して塗るかによって

\[\mathrm{dp}[1][i]=C+\sum_{k=1}^{i-(K-1)} \mathrm{dp}[1][k] *(C-1) + \sum_{k=1}^{i-(K-1)} \mathrm{dp}[2][k]\]

\[\mathrm{dp}[2][i]=\sum_{k=i-(K-1)+1}^{i-1}\mathrm{dp}[1][k]*(C-1) + \sum_{k=i-(K-1)+1}^{i-1}\mathrm{dp}[2][k]\]

となります。これは \(\mathrm{dp}[1][*],\mathrm{dp}[2][*]\) の累積和を求めておけば \(O(1)\) で計算できるため、\(i\) の小さい順に求めることで全体で \(O(N)\) で求めることができます。