問題

考え方

単純に $dp[i][j] :=$ 駅 $i$ にいて連続する到着する駅の長さが $j$ の組み合わせの数というDPを考えると $O(NK)$ となるため、メモリも時間も足りない。

「状態数が多すぎるので、工夫して状態数を減らす」というテクニックを使う。

この単純なDPの遷移を見てみると斜めにそれぞれ遷移していることが分かる。長さ $[1,k-1]$ に含まれる組み合わせの数はまとめて状態を考えることができる。

よって

$sum[i] := i$ 番目までの $[1, k-1]$ の和の場合の数
$dp[i] := i$ 番目の長さ $0$ の場合の数

というDPを定義する。DPの初期値は $dp[0] = 1,\ sum[1] = 1$ となる。DPの遷移は

$dp[i+1] := dp[i] + sum[i]$
$sum[i+1] := dp[i] + sum[i] - dp[i+1-k]$

となる。長さが $K$ になった分の場合の数は長さ $[1, k-1]$ の和の場合の数から引くことが必要である。

DPの遷移が似たような状態になっていることに着目すると更新に累積和が使えるという気持ちになるかも。実際に $O(NK)$ 解の累積和の更新の様子に着目できると良いかもしれない。