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; } };