个人思路：
\(sum_i\) 表示前 \(i\) 个数的前缀和，推一下式子可知是要选若干对 \(l_i,r_i\)，使得 \(l_1 < l_2 <\dots < l_k \le r_k < \dots < r_2 < r_1\) 且 \(sum_{l_i} + sum_{r_i} = sum_n\times 2\)。
然后就不会做了。
正解：
\(pre_i\) 表示 \([1,i]\) 的和，\(suf_i\) 表示 \([i,n]\) 的和，选若干对 \(l_i,r_i\)，使得 \(l_1 < l_2 <\dots < l_k \le r_k < \dots < r_2 < r_1\) 且 \(pre_{l_i} = suf_{r_i}\)。
上面的做法遗漏了 \(a_i \le 0\)，所以 \(pre_i\) 和 \(suf_i\) 分别为从左往右单增和从右往左单增，不同的值成独立段。
显然，对于一个段 \([l_l, l_r]\) 和 \([r_l, r_r]\)，枚举选的对数 \(p\)，贡献为 \(\sum\limits_{0 \le p \le min(l_r-l_l+1, r_r-r_l+1)} C_{l_r-l_l+1}^p \cdot C_{r_r-r_l+1}^p\)。
所有段贡献的乘积即为答案。
时间复杂度 \(\Theta(n)\)
标签：CF1738E,pre,le,suf,sum,Addicts,单增,Balance From： https://www.cnblogs.com/Mysterious-Cat/p/17153432.html