题解

思路

先把“能否被区间减法清零”化为相邻三项的不等式，再依次建立枚举、最后两项动态规划和容斥压缩动态规划三种算法。

做法

1. 好数组的判定

令边界 $a_0=a_{n+1}=0$。答案的关键判定为

必要性显然：每次覆盖位置 $i$ 的区间长度至少为 $2$，所以同时覆盖 $i-1$ 或 $i+1$。充分性可按数组元素和强归纳证明：取第一个非零位置 $i$，区间 $[i,i+1]$ 与 $[i,i+2]$ 中至少有一种减法仍保持全部不等式，随后使用归纳假设。

2. 子任务 1：枚举数组

枚举 $(k+1)^n$ 个数组，逐个检查上述不等式。复杂度为 $O(n(k+1)^n)$。

3. 子任务 2：记录最后两个数

设 $dp[x][y]$ 表示已经生成一个前缀，最后两个数为 $x,y$ 的方案数。加入新数 $z$ 时，需要 $y\le x+z$。对固定的 $y,z$，合法的 $x$ 是一个后缀，因此对 $x$ 做后缀和即可在 $O(1)$ 完成一次转移。

在序列两端各补一个 $0$，共转移 $n+2$ 次，最后读取状态 $(0,0)$。复杂度为 $O(nk^2)$，空间复杂度为 $O(k^2)$。

4. 子任务 3：容斥并压缩状态

称位置 $i$ 在 $a_i>a_{i-1}+a_{i+1}$ 时为坏位置。对坏位置集合做容斥，只需记录被选入容斥集合的位置个数的奇偶性。

设 $dp_i[q][x]$ 表示处理到位置 $i$，当前值为 $x$，已指定坏位置数的奇偶性为 $q$ 的带符号前方案数。普通转移可以从上一层任意末值到达 $x$。若指定 $i-1$ 为坏位置，则从 $i-2$ 层的末值 $y$ 出发，中间值有

种选择，并翻转奇偶性。对 $x$ 从大到小扫描，用两层前缀累加即可把这部分转移降到 $O(1)$。

在右端补一个 $0$ 后，答案为偶数容斥项减去奇数容斥项：

复杂度为 $O(nk)$，空间复杂度为 $O(k)$。由于模数 $p$ 随测试用例变化，所有运算都必须使用当前输入的 $p$。

5. 正确性说明

普通转移枚举了不要求新坏位置的全部延伸；第二种转移恰好枚举把中间位置指定为坏位置的延伸，并翻转容斥符号。每个数组最终按其实际坏位置集合贡献 $(1-1)^c$：没有坏位置时贡献 $1$，否则贡献 $0$。因此留下的正是全部好数组。

复杂度

• 子任务 1：时间 $O(n(k+1)^n)$，空间 $O(n)$；
• 子任务 2：时间 $O(nk^2)$，空间 $O(k^2)$；
• 子任务 3：时间 $O(nk)$，空间 $O(k)$。