概要：求めるべき準急の停車駅の停車パターンに対して，その「停車」と「通過」を反転させたものを \(1\) 対 \(1\) に対応させることができる．求めるべき停車パターンの代わりに，そちらを数え上げる．

求めるべき準急の停車駅の停車パターンの条件を整理すると，以下の通りです．

• 駅は \(1\) から \(N\) までの \(N\) 駅であり，それぞれに対して「停車」か「通過」のいずれかを割り振る．
• 駅 \(1\) と駅 \(N\) には必ず「停車」を割り振る．
• 連続する \(K\) 駅を「停車」に割り振ってはならない．

これに対して，準急の停車駅の停車パターンを反転させたもの（すなわち，元の停車パターンで「通過」だったものを「停車」に，「停車」だったものを「通過」にする）を考えます．ただし，駅 \(1\) および駅 \(N\) を「通過」とする，というのは事実上不可能なので，必ず停車する仮想の駅 \(0\) と \(N + 1\) を用意します．このとき，条件は以下の通りとなります：

• 駅は \(0\) から \(N + 1\) までの \(N + 2\) 駅であり，それぞれに対して「停車」か「通過」のいずれかを割り振る．
• 駅 \(0\) と駅 \(N + 1\) には必ず「停車」を割り振る．
• 駅 \(1\) と駅 \(N\) には必ず「通過」を割り振る．
• 連続する \(K\) 駅を「通過」に割り振ってはならない．

こちらの停車パターンを数え上げることにします．\(dp[i] =\) (最後に停車した駅が \(i\) である停車パターンの数) という DP を考えます．

このとき，この DP はひとつ前の停車駅で場合分けをすることにより

• \(dp[i] = \sum_{\max(0, i - K) \leq j \leq i - 1}dp[j] (2 \leq i \leq N - 1)\)

と遷移できます．（駅 \(0, 1, N, N + 1\) は特別な扱いをする必要があることに注意）

この DP の遷移元は区間和の形で表される形をしているので，累積和を計算しておくことで \(1\) 回あたり \(O(1)\) で遷移を行うことができます．これにより \(O(N)\) でこの問題を解くことができます．