题解

思路

只关注操作后真正改变的位置。

做法

设 $dp[i][d]$ 表示最后一个改变的位置是 $i$，且该位置相对原值增加了非零量 $d$ 的不同结果数。第一个改变位置 $i$ 的增量，只可能是它之前某个被选中的非零原值；相同数值造成相同结果，因此对前缀出现过的不同非零值各加入一次。

若状态 $(i,d)$ 中选中元素后的前缀和 $s=A_i+d$ 非零，那么任意后续位置 $k$ 被选中时都会改变，且增量唯一为 $s$。若 $s=0$，则可在 $i$ 与下一改变位置 $k$ 之间先选择一个非零元素而不改变它，随后 $k$ 的增量等于这个元素的原值；仍只需枚举区间内出现过的不同非零值。原序列本身始终可由只选一个位置得到，所以答案为 $1+\sum dp[i][d]$。

复杂度

增量范围不超过 $[-1000,1000]$，按上述转移实现即可；时间复杂度 $O(N^3\max|A_i|)$，空间复杂度 $O(N^2\max|A_i|)$。