計算量が \(O(N^{2} \max(|A_{i}|))\) の解法があります。公式解説の方針でも計算量削減が可能だと思われますが、自分の方針を記すことにします。

\(\mathrm{dp1}[i][j]\) : 前から \(i\) 番目まで見て、累積和が \(j\) であるような非空な部分列の選んだときの変化後の \(A\) の場合の数

\(\mathrm{dp2}[i][j]\) : 前から \(i\) 番目まで見て、累積和が \(j\) かつ、末尾が \(j\) であるような非空な部分列の選んだときの変化後の \(A\) の場合の数、言い換えると末尾を除くと和が \(0\) になるような部分列の選んだときの変化後の \(A\) の場合の数

初期値は \(\mathrm{dp1}[0][0] = 1\) で、その他は \(0\) です。

\(\mathrm{dp1}[i][*], \mathrm{dp2}[i][*]\) がわかっているときに、\(\mathrm{dp1}[i + 1][*], \mathrm{dp2}[i + 1][*]\) が求められれば良いです。

\(A_{i + 1}\) を累積和に入れないときの更新は簡単で、全ての \(j\) について以下の更新をすれば良いです。

\(\mathrm{dp1}[i + 1][j] += \mathrm{dp1}[i][j]\)

\(\mathrm{dp2}[i + 1][j] += \mathrm{dp2}[i][j]\)

\(A_{i + 1}\) を累積和に入れるとき、\(j \neq 0\) であるなら以下のように更新すれば良いです。

\(\mathrm{dp1}[i + 1][j + A_{i + 1}] += \mathrm{dp1}[i][j]\)

\(j = 0\) のときについて

まず、\(A_{i + 1} = 0\) のときは、意味がないので更新しません。\(A_{i + 1}\) と同じ要素が以前出ているときに、それが部分列の末尾に存在しているかつ、累積和が \(A_{i + 1}\) であるときと被ってしまうので、以下のように更新します。

\(\mathrm{dp1}[i + 1][A_{i + 1}] += \mathrm{dp1}[i][0] - \mathrm{dp2}[i][A_{i + 1}]\)

\(\mathrm{dp2}[i + 1][A_{i + 1}] = \mathrm{dp1}[i][0]\)

以上より、dp の更新が \(O(N^{2} \max(|A_{i}|))\) で可能です。

\(\mathrm{dp1}[N][j]\) は、累積和が \(j\) であるような部分列を選んだときの変化後の \(A\) の場合の数です。これの総和では、先ほどの \(j \neq 0\) のときと同様に被りが生まれます。よって、答えは以下の値になります。

\(\mathrm{sum}(\mathrm{dp1[N]}) - \mathrm{sum}(\mathrm{dp2[N]})\)

C++ 実装例