問題リンク
問題概要
長さNの数列\(A_1,,,A_N\)が与えられる。
\(1 \leqq L \leqq R \leqq N\)に対し、\(f(L,R)\)を\(A_L\)から\(A_R\)までの数を使って和をSにする組み合わせの総数とする。
\(f(L,R)\)の総和を求めよ。
解法
各組み合わせに対し、それを含むような\((L,R)\)がいくつあるかを考える。
例えば、ちょうど\(A_s\)から始まって\(A_t\)で終わるような物は、\(L \leqq s\) かつ \(t \leqq R\)を満たすもの全てに含まれるので、\(s \times (N+1-t) \)回カウントしたい。
次のようなDPを考える。
\(dp[i][j] = (i番目までの数字を使って和をjにする方法の総数)\)
初期状態は
\(dp[0][0] = 0\)
であり、遷移は
\(dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]] \)
ただし、i番目の数字から始まる組み合わせ総数に関してはi倍したいので、そこだけは
\(dp[i][A[i]] = dp[i-1][A[i]] + i \times dp[i-1][0]\)
とする。
最終的な答えは、ちょうどk番目で終わる物に関しては(N+1-k)倍したいので
\( \displaystyle \sum_{k=1}^{N} (dp[k][S] - dp[k - 1][S]) \times (N+1-k)\)
となる。
提出
https://atcoder.jp/contests/abc159/submissions/11112024
感想
これは割と得意なタイプだった。
