Infinite Stairs [yukicoder 1011]

https://yukicoder.me/problems/no/1011

前提知識

• 累積和を用いた動的計画法高速化

解説

https://yukicoder.me/submissions/447477

10⁹+7数え上げ、かつ、既視感のある問題なので、DP解法から考え始める。
すると、以下のDPなら解けることが分かる。

dp[turn][i] := 行動をturn回行って、i段目にいる移動方法の組み合わせ
これの遷移は、1回の行動で何階分移動するかでd通りになる。
これで状態数がO(dN²)で、遷移がO(d)となるため、状態数は解ける範囲内だが、遷移まで入れると間に合わない。
遷移の更新分を高速化することで、解くことはできないだろうか。
まずは、このDPの更新式。

    dp[0][0] = 1;  
    rep(turn, 0, N) rep(i, 0, K + 1) rep(delta, 1, d + 1) {  
        dp[turn + 1][i + delta] += dp[turn][i];  
    }  

これは配るDPになっているので、貰うDPに変換する。
配るDPとは遷移元から遷移先を更新していく形で、遷移先に添え字の差分が入る。
貰うDPとは遷移先から遷移元を参照して更新していく形で、遷移元に添え字の差分が入る。

    dp[0][0] = 1;  
    rep(turn, 0, N) rep(i, 0, K + 1) {  
        rep(delta, 1, min(i, d) + 1) dp[turn + 1][i] += dp[turn][i - delta];  
    }  

これを見ると、1つ前のターンのある区間の総和を使って更新していることが分かる。
区間の総和は事前に累積和を取っておけば計算可能だ。

ターンの頭で以下の累積和を取っておこう。
tot[turn][i] := dp[turn][0] + dp[turn][1] + ... + dp[turn][i]
あとは、これを使ってdelta変数を使ったfor文部分を累積和による更新に置き換えると更新がO(1)となって間に合う。

int N, d, K;
mint dp[303][101010];
mint tot[303][101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> d >> K;
    
    dp[0][0] = 1;
    rep(turn, 0, N) {
        tot[turn][0] = dp[turn][0];
        rep(i, 1, K + 1) tot[turn][i] = dp[turn][i] + tot[turn][i - 1];
        rep(i, 1, K + 1) {
            dp[turn + 1][i] = tot[turn][i - 1];
            if (0 <= i - d - 1) dp[turn + 1][i] -= tot[turn][i - d - 1];
        }
    }

    cout << dp[N][K] << endl;
}