题解

思路

切分线与前缀和

记前缀和

$$P_0=0,\qquad P_i=\sum_{j=1}^{i}a_j,$$

总和为 $S=P_n$。只考虑内部切分线 $1,2,\ldots,n-1$。

从一个平衡划分的最外层开始同时去掉首段和末段。若去掉后左侧恰好经过切分线 $i$，右侧恰好经过切分线 $j$，因为两侧已经去掉的段两两等和，必有

$$P_i=S-P_j,$$

也就是 $P_i+P_j=S$。继续向内去掉一对段，左切分线严格向右、右切分线严格向左。

反过来，任何满足上述条件的嵌套切分线对序列，都唯一确定一种平衡划分：相邻两层前缀和之差就是一对相等的段和；最后未处理部分作为中间一段，或者两侧在同一切分线相遇。

因此问题转化为：统计内部切分线按前缀和值分组后，可以组成多少条嵌套链。

同一对互补前缀和值

固定 $x<S-x$。设内部切分线中有 $A$ 条满足 $P_i=x$，有 $B$ 条满足 $P_j=S-x$。

由于数组元素非负，前缀和单调不降，而且 $x<S-x$，所以所有第一组切分线都在第二组之前。

若在这一层取 $k$ 对切分线，需要：

• 从左侧 $A$ 条中选出 $k$ 条，按下标递增使用；
• 从右侧 $B$ 条中选出 $k$ 条，按下标递减使用。

方案数为 $\binom Ak\binom Bk$。允许这一层一对也不取，于是总数为

$$\sum_{k\ge0}\binom Ak\binom Bk =\binom{A+B}{A}.$$

不同的 $x$ 按数值从小到大时，切分线天然继续向内嵌套，所以各层方案数可以直接相乘。

正中间的前缀和值

若 $S$ 为偶数并且存在 $P_i=S/2$ 的内部切分线，设这样的切分线共有 $M$ 条。

此时任取这些切分线的一个子集，按下标从两端向中间配对；若子集大小为奇数，最中间那条切分线就是左右两侧相遇的位置。每个子集与一种正中间的嵌套方式一一对应，因此该层贡献

$$2^M.$$

空子集也必须计入，因为可以不在这一层继续切分。所有层均取空时，对应完全不切分的方案。

最终答案为

$$\left(\prod_{x<S-x,\,c_xc_{S-x}>0} \binom{c_x+c_{S-x}}{c_x}\right) \times \begin{cases} 2^{c_{S/2}},&S\text{ 为偶数};\\ 1,&S\text{ 为奇数}. \end{cases}$$

其中 $c_x$ 表示内部切分线里前缀和等于 $x$ 的条数。

做法

三个算法层级

子任务 1：枚举切分集合

枚举 $n-1$ 条内部切分线的所有子集，实际算出每段和并检查是否为回文。复杂度 $O(n2^n)$。

子任务 2：组合分组 + 杨辉三角

使用上述组合公式，但用杨辉三角预处理 $0\le i\le2000$ 的全部组合数。复杂度 $O(n^2+\sum n)$，空间复杂度 $O(n^2)$。

子任务 3：组合分组 + 阶乘逆元

预处理阶乘和逆阶乘，在 $O(1)$ 时间求一个组合数。每组测试只需扫描内部前缀和并统计相同值的连续段。总时间复杂度 $O(\sum n)$，空间复杂度 $O(\max n)$。

正确性证明

引理 1：平衡划分每去掉若干对最外层段后，对应的左右切分线 $i,j$ 满足 $P_i+P_j=S$。

证明：已去掉的左侧段和之和等于已去掉的右侧段和之和，分别为 $P_i$ 与 $S-P_j$。故结论成立。

引理 2：一条满足左下标严格递增、右下标严格递减且每对切分线均满足 $P_i+P_j=S$ 的嵌套链，唯一对应一个平衡划分。

证明：相邻两层左侧前缀和之差等于相邻两层右侧后缀和之差，所以得到的两段和相等。最内层剩余区间作为唯一中段，或两边在一条切分线相遇。所有切分线都被唯一确定，故对应关系唯一。

引理 3：对于 $x<S-x$ 的一组互补前缀和值，其所有选择的总方案数为 $\binom{A+B}{A}$。

证明：取 $k$ 对时左右各独立选择 $k$ 条切分线，共 $\binom Ak\binom Bk$ 种。对 $k$ 求和并用范德蒙德恒等式即得结论。

引理 4：对于 $x=S/2$ 的 $M$ 条内部切分线，其贡献为 $2^M$。

证明：任意切分线子集按两端向中间配对，唯一形成嵌套链；反之链使用的切分线集合也唯一。因此与全部子集一一对应。

定理：算法输出恰为所有平衡划分的数量。

证明：由引理 1、2，平衡划分与所有合法嵌套链一一对应。不同的互补前缀和值层之间天然嵌套且选择独立；由引理 3、4，各层贡献分别为对应组合数或二次幂。相乘即统计全部且不重不漏。

复杂度

• 子任务 1：时间复杂度 $O(n2^n)$，空间复杂度 $O(n)$。
• 子任务 2：预处理杨辉三角的时间、空间复杂度均为 $O(n^2)$，处理所有测试数据另需 $O(\sum n\log n)$ 时间。
• 子任务 3：阶乘预处理 $O(N)$；使用有序映射实现时总时间复杂度为 $O(\sum n\log n)$，空间复杂度为 $O(N)$。独立双指针实现可达到 $O(\sum n)$ 总时间。