操作後に出来上がる数列の各要素が、元の数列の区間和になっていることから、問題を次のように読み替えることができます。

「数列の途中にいくつか仕切りを入れる。仕切りに挟まれた各区間で和を取り新しい数列を作る。何種類作れるか？」

この操作は、例えば \(A=(1,2,3,-1,1,0)\) のとき、\( (1,2,3 \mid -1,1 \mid 0)\) と \(2\) 箇所に仕切りを入れ \((6,0,0)\) という数列を得る、というようなものになります。

ここで次のようなDPを考えます。

\(DP[i]= A_1,\ldots,A_i\) から操作によって作ることができる数列の種類数

\(DP[i]\) から \(DP[i+1]\) を得る方法を考えます。新たに \(A_{i+1}\) という要素が使えるようになったことで、どのような数列が作れるようになったかというと

• \(A_{i+1}\) の直前に仕切りを入れる。すなわち、\(A_1,\ldots,A_i\) から作った数列の末尾に \(A_{i+1}\) を追加する
• \(A_{i+1}\) の直前に仕切りを入れない。すなわち、 \(A_1,\ldots,A_i\) から作った数列の末尾の要素に \(A_{i+1}\) を加算する

の \(2\) 種類が考えられます。

この \(2\) 種類の例を挙げておきましょう。\(A=(1,2,4)\) で \(i=2\) のときを考えます。\((1,2)\) から作ることができる数列は \((1,2),(3)\) の \(2\) 種類です。それぞれについて、

• 末尾に \(A_3=4\) を追加する。すなわち、\((1,2,4),(3,4)\) を作る
• 末尾の要素に \(A_3=4\) を加算する。すなわち、\((1,2+4),(3+4)\) を作る

となります。この例を見ると、\(DP[i+1]=DP[i]*2\) になるように思えます。本当にそうでしょうか？　別の例を見てみましょう。

\(A=(1,0,4)\) で \(i=2\) のときを考えます。\((1,0)\) から作ることができる数列は \((1,0),(1)\) の2種類です。そのそれぞれについて、

• 末尾に \(A_3=4\) を追加する。すなわち、\((1,0,4),(1,4)\) を作る
• 末尾の要素に \(A_3=4\) を加える。すなわち、\((1,0+4),(1+4)\) を作る

となり、\((1,4)\) という数列を重複して数えてしまうことになります。このようなことが起こるのは、\(A_{i+1}\) を追加する前の数列が長さ \(2\) 以上で末尾の要素が \(0\) であったとき、かつ、そのときに限ります。したがって正しい漸化式は
\(DP[i+1]=DP[i]*2- DP[i]\text{ のうち長さ 2 以上で末尾の要素が 0 である数列の種類数}\)
となります。この「\(DP[i]\) のうち長さ \(2\) 以上で末尾の要素が \(0\) である数列の種類数」は求められるでしょうか？

ここで、「操作後の数列が長さ \(2\) 以上かつ末尾が \(0\) であるとき、その \(0\) は極小な区間を使って作る」としてよいです。つまり \(A=(1,2,-2,3,-3)\) という数列から \((1,0)\) を作る時、仕切りの入れ方は \((1\mid 2,-2,3,-3)\) ではなく、 \((1,2,-2\mid 3,-3)\) だとしてよいです。
したがって、\(A[k+1]+\ldots+A[i]=0\) を満たす \(i\) 未満の数 \(k\) が存在する時、その最大値を \(f(i)\) とすると、求める数列の個数は \(DP[f(i)]\) になります(ただし \(DP[0]=0\) とする)。また、そのような \(k\) が存在しないとき \(0\) であることがわかります。

以上より、\(DP[i+1]=DP[i]*2-DP[f(i)]\) という漸化式が得られました。\(f(i)\) は累積和などを用いて \(O(N\log N)\) で前計算することができるので、全体で \(O(N\log N)\) でこの問題が解けました。

実装上は \(A[k+1]+\ldots+A[i]=0\) を満たす \(i\) 未満の数 \(k\) が存在しないとき、\(f(i)=0\) と定めると簡略化することができます。(\(DP[0]=0\) なので)

実装例(Python)