まず、すべてのマスが白である場合、移動方法が何通りあるか考えます。これは簡単です。以下のような動的計画法を考えます。

\(\mathrm{dp1}_{i}:=\) \(( \ i\) マス目に到達する移動方法の数 \()\) とします。\(\mathrm{dp1}_1 = 1\) として、遷移は、

\[ \mathrm{dp1}_{i} = \sum_{k=1}^{K} \mathrm{dp1}_{i-k} \]

となるので、この通り計算すればよいです（添字が非正になる場合は適当に調整します）。

さて、元の問題について考えましょう。先ほど同様、動的計画法によるアプローチを試みます。

\(\mathrm{dp2}_{i}:=\) \(( \ N=i\) であった場合の答え \()\) とします。便宜上、\(\mathrm{dp2}_1 = 1\) としておきます。

ある \(i \ (1 \leq i \leq N)\) と \(k \ (1 \leq k \leq K)\) に対し、\(\mathrm{dp2}_{i-k}\) が \(\mathrm{dp2}_{i}\) の値にどれだけ寄与するか考えます。

ここで、以下の事実に注目してみましょう。

• マス \(i-k\) からマス \(i\) にジャンプするためには、マス \(i-k, i\) はともに白色でなければならないが、逆に、その間にある「飛ばすマス」は白黒どちらでもよい

飛ばすマスの色はどれも \(2\) 通りのうちから自由に決められるので、\(\mathrm{dp2}_{i-k}\) の \(2^{k-1}\) 倍が \(\mathrm{dp2}_{i}\) の値に加えることが分かりました（この考え方は、「主客転倒」と呼ばれることがあります）。

よって、以下のような遷移式が導かれます。

\[ \mathrm{dp2}_{i} = \sum_{k=1}^{K} 2^{k-1} \mathrm{dp2}_{i-k} \]

これを愚直に計算すると時間計算量が \(\mathrm{O}(NK)\) となり間に合いませんが、\(\sum_{k=1}^{K} 2^{k-1} \mathrm{dp2}_{i-k}\) の値を持ちつつうまく「スライド」させるように計算することで、\(\mathrm{O}(N)\) 時間で計算することが出来ます。詳しくは実装例を参考にしてください。

実装例（Python3）