复制或前缀和 题解

思路

处理到位置 $i-1$ 时，以当前前缀和 $s$ 为状态。对 $b_i$ 有两种转移：令 $a_i=b_i$，新前缀和为 $s+b_i$；或令当前前缀和等于 $b_i$，新前缀和为 $b_i$。当且仅当 $s=0$ 时，两种选择得到同一个 $a_i$，必须只计一次。

做法

子任务 1 枚举每个位置采用哪种条件，显式构造数组并去重。

子任务 2 显式保存所有可能前缀和及方案数，每轮遍历全部状态完成两种转移，复杂度 $O(n^2)$。

满分算法令所有状态统一带一个偏移量。第一类转移只需把偏移量增加 $b_i$；第二类转移把“当前总方案数减去旧前缀和为零的方案数”加入实际前缀和 $b_i$ 对应的状态。哈希表只新增一个相对键，因此每轮期望 $O(1)$。

正确性证明

每个混合数组在位置 $i$ 必然由上述两种条件之一产生。若旧前缀和非零，两种条件给出的 $a_i$ 不同；若旧前缀和为零，两种条件都给出 $a_i=b_i$，只应保留一次。递推恰好对这一重合部分减重，故每个不同数组被计数一次。偏移量只是同时平移第一类转移的所有前缀和，不改变方案数，因而优化后的递推等价且正确。

复杂度

每个测试用例期望时间复杂度 $O(n)$，空间复杂度 $O(n)$。