累積和 DP
こういう名前がついているというよりは、こういう技術を活用するものだと思ってもらえればと思う。
DP における重たい更新
例えば、以下の問題を考える。
以下のような数列$ Aが何通りあるか$ \bmod\ 998244353で答えよ。
・$ |A| = N
・$ 1 \leq A_i \leq N
・$ \Sigma_{k=1}^{N} A_k \leq M
ただし、$ 1 \leq N, M \leq 3000
この問題を解くための DP は以下の通りで良いだろう。
$ \mathrm{DP}[i][j] = i 番目の要素まで決めていて、総和が$ jであるような数列の通り数
しかし、これをナイーブに更新しようとすると以下のようになる。
code:cpp
for(int i = 0; i < n; i++){
for(int j = 0; j <= m; j++){
for(int x = 1; x <= n; x++){
if(j + x > m) break;
}
}
}
この DP を更新するために必要な時間計算量は$ \Omicron(N^2M)となってしまい、TLE になってしまう。
高速化
そういえば、更新先の$ j の添字は区間になっていて、$ [j+1:\mathrm{min}(M, j+N)] となる。
また、$ \mathrm{DP}[i] の更新中に$ \mathrm{DP}[i] を参照することはない。
よって、累積和(今回は imos 法のそれ)を用いて更新を高速にできる。
具体的には以下のようになる。
code:cpp
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
}
}
ただしmint dp[n + 1][m + 2]と宣言していることを想定している。
類題