Shirogane 想唱歌

由于总误差不超过 $E$，每一项都满足 $|A_i-B_i|\le E$。因为 $0\le A_i\le50$ 且 $B_i\ge0$，所有可能的音高均在 $L=0$ 到 $U=50+E$ 的范围内。该范围包含 $W=51+E\le101$ 个整数。

设 $D_i(e,x)$ 表示确定前 $i$ 项后，总误差恰好为 $e$，且最后一个音高 $B_i$ 为 的序列数量。只保存满足 、 的状态。

第一个音高固定为 $B_1=0$，因此第一项的误差为 $A_1$。若 $A_1\le E$，则初始化

$$D_1(A_1,0)=1.$$

其余状态均为 $0$。若 $A_1>E$，则不存在合法序列，可以直接输出 $0$。

现在设 $i\ge2$，并将最后一个音高选为 $x$。这一项的误差为 $d=|A_i-x|$，因此前 项的总误差必须为 。前一个音高 必须满足 ，所以当 时，

$$D_i(e,x)=\sum_{y=\max(L,x-K)}^{\min(U,x+K)}D_{i-1}(e-d,y).$$

当 $e<d$ 时，该状态的值为 $0$。

按照 $i=2,3,\ldots,N$ 的顺序，枚举每个误差 $e$ 和最后一个音高 $x$，再直接枚举上述区间内的 $y$ 并求和。所有加法均对 $1$ 取模。

最终答案为

$$\sum_{e=0}^{E}\sum_{x=L}^{U}D_N(e,x).$$

应当将误差不超过 $E$ 的所有状态相加，而不是只统计误差恰好为 $E$ 的状态。

共有 $N(E+1)W$ 个状态，每个状态最多检查 $2K+1$ 个前一个音高。因此，时间复杂度为

$$O\bigl(N\cdot W\cdot(E+1)\cdot(2K+1)\bigr).$$

这些因子分别对应元素个数 × 音高范围 × 总误差范围 × 相邻音高差范围。在给定限制下，可以直接计算这些转移。

每一步只使用紧接着的上一步，所以只需保存两层数组。空间复杂度为 $O(W(E+1))$。将音高 $x$ 对应到数组下标 $x-L$ 即可。

证明

第一项唯一确定为 $0$，其误差为 $A_1$。因此，在 $A_1\le E$ 时设置 ，恰好统计了唯一合法的长度为 的序列。若 ，后续项无法减小总误差，因此答案为 。

Solution written by GPT6