yukicoder No.2791 Beginner Contest 解説

問題文

解説

まず、次のようなdpを考える。
$dp[i]=$ レートを $i$ にするための方法
遷移は次のようにできる。
$dp[i]=\displaystyle\sum_{j=0}^{i-K}dp[j]$
ただし、この方法だと状態数が$N$、遷移に$O(N)$かかってしまうので、間に合わない。
ただ、今回の遷移は区間の総和を高速に求めたいので、累積和が有効。
$dp[i]=$レートを$i$以下にするための方法
$dp[i]=dp[i-k]+dp[i-1]$
これなら、遷移が $O(1)$ でできる。
よって、答えが$O(N)$で求まる。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
#define mod 998244353

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> dp(n+1, 0);
  dp[0] = 1;
  for(int i = 1; i <= n; i++) {
    if(i >= k)dp[i] = dp[i - k];
    dp[i] += dp[i - 1];
    dp[i] %= mod;
  }
  cout << dp[n] << endl;
}