TDPC F - 準急

考え方

ABCでいうと、E問題級。

停車する駅よりも通過する駅に注目する方が簡単。
DPテーブルに持たせるデータを「その駅までルール通りに進み、その駅を通過するパターン数」とする。
すると更新は、基本的には直前 $K$ 駅の値の和を取ればよいだけだということになる。

ただし、いくつか問題がある。
まず、上で書いたことを愚直にやると、$O(NK)$ かかってしまう点。
これを高速化するには、区間和の長さが（はみ出る部分を除き）一定であることが利用できる。
区間和の長さが $K$ になるまでは普通に直前までの和を保管しておけば $1$ 駅あたり $O(1)$。
その先はsliding window法を用いれば、やはり $1$ 駅あたり $O(1)$。
これで、全体の計算量が $O(N)$ となる。

そしてもう $1$ つ、最初の駅と最後の駅には必ず停車することが条件になっている点。
停車側に注目するので、DPテーブルの初期条件の設定が難しいのと、最後の集計が難しいことが問題。
しかしこれは、その前後にさらに確定で通過する駅を番兵的に用意しておくことで解決する。
片側の通過駅の通過方法を $1$ 通りとしてスタートして、逆側の通過駅の通過方法数を答えればよい。
確定停車駅の通過方法は $0$ であることを忘れずに処理すること。

計算量は $O(N)$。

入力例1での動作

入力を受け取る。

n: 10
k: 2

dp[i] を、駅 $i$ までルール通りに進み、駅 $i$ を通過するパターン数とする。
駅 $0$ と駅 $11$ は、番兵として通過する駅とする。
駅 $1$ と駅 $10$ は必ず停車するので、dp[1] と dp[10] は $0$ になる。

今回は $K=2$ なので、駅 $i$ を通過するとき、その直前に通過した駅は $i-2$ または $i-1$ である。
この $2$ 個の値の和をsliding window法で管理しながら更新する。

DP テーブルは次のようになる。

例えば、駅 $4$ では次の計算になる。

dp[4] = dp[2] + dp[3]
      = 1 + 1
      = 2

次の駅 $5$ へ窓をずらすと、駅 $2$ の $1$ 通りを外し、駅 $4$ の $2$ 通りを加える。
したがって、区間和は $2-1+2=3$ となり、駅 $5$ を通過する方法は $3$ 通りになる。

駅 $10$ は必ず停車するので dp[10] = 0 とする。
最後の番兵では、次の計算になる。

dp[11] = dp[9] + dp[10]
       = 21 + 0
       = 21

したがって、答えは $21$。

注意点

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算や引き算をするたびに結果を % 1000000007 する。
引き算で負になることがあるので、負数を補正する。

別解

特になし。