题解

思路

转化

每次合并相邻元素，等价于把原序列划分成若干个非空连续段，并把每段替换为它的区间和。

令前缀和为 $S_i=A_1+\cdots+A_i$。一个分段结果的前缀和序列，恰好是在 $S_1,S_2,\ldots,S_{N-1}$ 中选择一个子序列，再在末尾固定追加 $S_N$。结果序列与其前缀和序列一一对应，固定追加同一个 $S_N$ 也不会改变不同序列的数量。因此问题变为：求序列 $S_1,S_2,\ldots,S_{N-1}$ 的不同子序列数量，空子序列也计入。

做法

动态规划

设 $D_i$ 表示前 $i$ 个前缀和能够形成的不同子序列数量，初始 $D_0=1$。

加入 $S_i$ 时，原有每个子序列都可以选择不追加或追加 $S_i$，暂时得到 $2D_{i-1}$。若 $S_i$ 上一次出现在位置 $p$，那么以这两个相同值分别作为最后一次追加所产生的重复部分，恰好有 $D_{p-1}$ 个；没有出现过则无需扣除。因此

用映射记录每个前缀和值最后出现的位置，即可在线计算。

对于 $N\le20$，可以枚举全部分界选择并把得到的块和序列放入集合。对于 $N\le2000$，可向前扫描寻找相同前缀和，使转移达到平方复杂度。若所有 $A_i>0$，前缀和严格递增，不会出现重复，答案直接是 $2^{N-1}$。

正确性证明

任意操作只会合并相邻块，所以最终每个元素都是原序列某个连续段的和；反之，按任意连续分段依次合并段内元素都能得到对应结果。因此分段与可达结果完全对应。

一个分段结果的前缀和，正是原前缀和序列中所有分界位置对应的值，再追加固定的总和 $S_N$。前缀和变换可逆，所以不同结果序列与 $S_1,\ldots,S_{N-1}$ 的不同子序列一一对应。

转移中，不追加 $S_i$ 保留全部 $D_{i-1}$ 个子序列，追加则再产生同样数量。若存在最近的相同值 $S_p=S_i$，重复的恰是由前 $p-1$ 个元素任取子序列后追加该值的 $D_{p-1}$ 种；更早的重复已包含在这组中。扣除后每种子序列恰计一次，递推正确。

复杂度

映射实现的时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。