Typical DP Contest - F 準急

F: 準急 - Typical DP Contest | AtCoder

const int MOD = (int)1e9+7;
class f_semi_express {
public:
    //
    // dp[i][k] := i 番目にとまり k 駅連続で停車する組み合わせ数
    //
    // として計算できる。しかしこれだと O(N*K) なので間に合わない
    //
    void solve_TLE(void) {
            int N,K;
            cin>>N>>K;
            vector<vector<int>> dp(N+1,vector<int>(K, 0));

            dp[1][1] = 1;
            for (int i = 1; i < N; ++i)
            for (int k = 0; k <= K-1; ++k)
            {
                if (k+1 <= K-1)
                    (dp[i+1][k+1] += dp[i][k]) %= MOD;
                (dp[i+1][0] += dp[i][k]) %= MOD;
            }
            int res = 0;
            FOR(k, 1, K)
                (res += dp[N][k]) %= MOD;
            cout<<res<<endl;
    }
    //              K-1
    // 最終的な答えが ∑ dp[N][k] なので
    //              k=1
    //         K-1
    // dp2[i] = ∑ dp[i][k]  とすると
    //         k=1
    //
    // dp[i][K-1] = dp[i-1][K-2] = ... = dp[i-K+1][0] or dp[0][K-i-1]
    // dp2[i+1] = dp[i][0] + dp[i][1] + ... + dp[i][K-2]
    //          = dp[i][0] + dp2[i] - dp[i][K-1]
    // dp[i+1][0] = dp2[i] + dp[i][0]
    //
    // と k のループを消せる
    //
    // O(N)
    void solve(void) {
            int N,K;
            cin>>N>>K;

            vector<int> dp(N+1,0); // dp[i][0]
            vector<int> dp2(N+1, 0);

            dp[0] = 1;  // solve_TLE では参照されないので不要だが、dp[1][1] = dp[0][0] = 1 なので、これがないとダメ
            dp2[1] = 1;
            for (int i = 1; i < N; ++i)
            {
                int dpK1 = (i>=K-1)? dp[i-K+1] : 0;
                dp2[i+1] = ((dp[i] + dp2[i])%MOD - dpK1 + MOD) %MOD;
                dp[i+1]  = (dp2[i] + dp[i])%MOD;
            }
            cout<<dp2[N]<<endl;
    }
};