出来上がる数列を一つの操作列に対応させることを考えます。 ある空でない数列を作ろうと思ったとき、作りたい数列の一番左の値ができるまで \(A\) の一番左の値と二番目に左の値を足し合わせ、それから作りたい数列の二番目に左の値ができるまで \(A\) の二番目に左の値と三番目に左の値を足し合わせ、\(\cdots\) という貪欲法を行うことにします。作りたい数列のどの要素にも対応していない \(A\) の接尾辞が残ることがありますが、その和が \(0\) であれば作りたい数列は作ることができ、そうでなかった場合作ることができません。この貪欲法の操作列と出来上がる数列は一対一に対応しているので、貪欲法の操作列として考えられるものの個数を求めれば良いです。

動的計画法を考えます。\(DP[i]\) を、貪欲法の操作列の接頭辞であって、\(A\) の \(i\) 番目の要素までが作りたい数列の要素に対応するような操作列の個数とします。すると、\(A[j]+A[j+1]+ \cdots +A[i]=0\) になるような最大の \(j(<i)\) に対して、\(DP[i]=DP[j]+DP[j+1]+ \cdots + DP[i-1]\) となります。\(k(<j)\) に対して \(A[k]\) から \(A[j-1]\) までの和は \(A[k]\) から \(A[i]\) までの和と等しく、貪欲法では前者が一つの要素に対応するため、\(DP[k]\) からは \(DP[i]\) に遷移しません。

\(j\) を求めるには、\(A\) の左からの累積和を計算し、累積和ごとに \(i\) より小さいものの中で最大の添字をmapなどで管理しておけば良いです。また、\(DP\) の左からの累積和を計算していくことで、\(DP[i]\) の計算が \(O(1)\) でできるようになります。

答えは \(A[k]+A[k+1]+ \cdots +A[N]=0\) となるような \(k(>0)\) に対する \(DP[k]\) の和になります。計算量は \(O(NlogN)\) や \(O(N)\) です。