AtCoder ABC 159 F
問題: https://atcoder.jp/contests/abc159/tasks/abc159_f 問題文が複雑ですが、\(A\)の要素のうち、\(L\)番目と\(R\)番目の間にあるものをいくつか選んで和を\(S\)にするような選び方の数が\(f(L, R)\)です。 すべての\(L, R\)について\(f(L, R)\)の和を求めるので、答えを\(Y_N\)として式にすると、 \[\begin{align} Y_N = \sum_{L=1}^N\sum_{R=L}^N f(L, R) \end{align}\] となります。 \(N\)の部分を変数にした\(Y_i\)を変形していきます。 \[\begin{align} Y_i &= \sum_{L=1}^i\sum_{R=L}^i f(L, R) \\ &= \sum_{L=1}^i\sum_{R=L}^{i-1} f(L, R) + \sum_{L=1}^i f(L, i) \\ &= \sum_{L=1}^{i-1}\sum_{R=L}^{i-1} f(L, R) + \sum_{L=1}^i f(L, i) \\ &= Y_{i-1} + \sum_{L=1}^i f(L, i) \end{align}\] \(g(i) = \sum_{L=1}^i f(L, i)\)とすると、\(Y_1 = \sum_{L=1}^1\sum_{R=1}^1 f(L, R) = \sum_{L=1}^1 f(L, R) = g(1)\)とあわせて、 \[\begin{aligned} Y_N &= Y_{N-1} + g(N) \\ &= Y_{N-2} + g(N) + g(N-1) \\ &= Y_1 + g(N) + g(N-1) + g(N-2) + ... + g(2) \\ &= \sum_{i=1}^N g(i) \end{aligned}\] となるので、各\(g(i)\)を動的計画法を使って求めていきましょう。 \(A\)の要素のうち、\(L\)番目と\(R\)番目の間にあるものをいくつか選んで和を\(s\)にするような選び方の数を\(z(L, R, s)\)として（\(f(L, R) = z(L, R, S