题解

思路

数组首尾的初值不会影响答案；真正决定分支合并的是 $a_2,a_3,\ldots,a_{n-1}$。

依次处理这些内部元素。设当前带符号状态为 $s$，本次处理的原始值为 $x$，令

两种操作分别把下一状态变成 $t$ 和 $-t$。当 $t\ne0$ 时，这两种选择会在已经确定的数组位置上留下不同的值，因此得到两个不同的前缀；当 $t=0$ 时，$t=-t$，两种操作得到完全相同的数组，只能计数一次。

于是只需维护每个带符号状态对应多少个不同的已确定前缀。初始时尚未处理内部元素，只有状态 $0$，计数为 $1$。处理一个 $x$ 时执行：

• 将当前计数加入状态 $s+x$；
• 如果 $s+x\ne0$，再将当前计数加入状态 $-(s+x)$。

所有加法都对 $998244353$ 取模。处理完 $a_2$ 到 $a_{n-1}$ 后，将全部状态的计数求和即为答案。

正确性证明

我们证明上述动态规划计算的恰是不同可达数组的数量。

对已经处理的内部元素个数归纳。初始时没有执行操作，空的已确定前缀只有一个，对应状态 $0$，结论成立。

假设处理前，dp[s] 等于状态为 $s$ 的不同已确定前缀数量。加入当前元素 $x$ 后，每个这样的前缀都可以选择两种操作，下一状态分别为 $s+x$ 与 $-(s+x)$。若 $s+x\ne0$，两种选择在本次确定的位置取值不同，所得前缀不同；若 $s+x=0$，两个状态以及本次确定的值都相同，两个选择产生同一前缀，必须只加入一次。来自不同旧前缀的结果仍在更早的已确定位置上不同，所以即使进入相同状态，其数量也应相加。因此转移后每个状态的计数仍准确。

归纳可知，全部内部元素处理完后，所有状态中的条目一一对应不同可达数组。对其计数求和即得所求。

做法

子任务 1 中 $n\le18$。可以枚举全部 $2^{n-2}$ 种操作序列，真实模拟数组，并用集合去重，复杂度为 $O(2^n n)$。

子任务 2 中内部元素之和不超过 $4000$。用有序映射只保存实际出现的带符号状态，按照上述递推转移，复杂度为 $O(nS\log S)$，空间复杂度为 $O(S)$，其中 $S=\sum_{i=2}^{n-1}a_i$。

完整数据中 $S\le 300\times298=89400$。用下标平移后的稠密数组表示 $[-S,S]$，每次清空下一层并滚动。

复杂度

• 完整枚举算法的时间复杂度为 $O(2^n n)$，集合占用 $O(2^n n)$ 空间。
• 稀疏映射动态规划的时间复杂度为 $O(nS\log S)$，空间复杂度为 $O(S)$。
• 稠密滚动动态规划的时间复杂度为 $O(nS)$，空间复杂度为 $O(S)$。