题解

\n## 思路

好数组的判定

在数组两端补 $a_0=a_{n+1}=0$。数组是好数组当且仅当

必要性很直接：每次覆盖位置 $i$ 的合法区间长度至少为 $2$，因此也会覆盖它的左邻或右邻。

充分性可对元素总和作强归纳。取最靠左的正数位置 $i$，则 $a_{i+1}>0$。在区间 $[i,i+1]$ 与 $[i,i+2]$ 中至少有一个减一后仍满足全部局部不等式；否则相邻两个失败条件会互相矛盾。执行该操作后总和减小，归纳即可将数组清零。

做法

子任务 1：枚举数组

枚举全部 $(k+1)^n$ 个数组，逐项检查局部不等式并计数。时间复杂度为 $O(n(k+1)^n)$。

子任务 2：二进制自动机

当 $k=1$ 时，每个元素只有 $0,1$ 两种取值。用最后两个二进制值作为四个状态，逐位加入新值并检查中间位置的不等式。最后再加入两个 $0$ 处理右边界。时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

子任务 3：直接三重转移

设 $dp(a,b)$ 表示已经生成某个前缀，最后两个元素为 $a,b$ 的方案数。加入 $c$ 时，仅当 $b\le a+c$ 才能转移到状态 $(b,c)$。在开头放入两个 $0$，处理完原数组后再加入两个 $0$，最终答案是 $dp(0,0)$。

直接枚举 $a,b,c$，时间复杂度为 $O(nk^3)$，空间复杂度为 $O(k^2)$。

子任务 4：前缀和优化

固定 $b,c$ 后，合法的 $a$ 满足

对每个固定的 $b$，预处理

即可在 $O(1)$ 时间求出所有合法 $a$ 的贡献。每一位只需枚举 $b,c$。

正确性证明

引理 1

好数组一定满足 $a_i\le a_{i-1}+a_{i+1}$。

证明。 任意一次使 $a_i$ 减一的操作长度至少为 $2$，必然同时使某个相邻位置减一。因此位置 $i$ 被覆盖的总次数不超过两个相邻位置被覆盖次数之和。$\square$

引理 2

满足全部局部不等式的非负整数数组一定是好数组。

证明。 对数组元素总和强归纳。总和很小时结论直接成立。取最靠左的正数位置 $i$；若操作 $[i,i+1]$ 会破坏位置 $i+2$ 的不等式，则有 $a_{i+2}>a_{i+3}$。这又保证操作 $[i,i+2]$ 不会破坏位置 $i+3$ 的不等式，其余位置显然不受影响。于是总能执行一次合法操作并保持全部不等式，再应用归纳假设。$\square$

引理 3

动态规划的状态 $dp(a,b)$ 恰好计数所有当前前缀合法且末两项为 $a,b$ 的数组。

证明。 加入 $c$ 时，唯一新得到完整左右邻居的位置是值为 $b$ 的位置；转移条件 $b\le a+c$ 正好验证它。其余已验证位置不变，尚未验证的只有新末项。归纳成立。$\square$

定理

算法输出全部好数组的数量对 $p$ 取模。

证明。 由引理 1、2，好数组与满足全部局部不等式的数组完全相同。由引理 3，动态规划逐一且不重复地计数这些数组；末尾加入两个 $0$ 后两端条件也被验证，故 $dp(0,0)$ 即所求。前缀和只改变求和方式，不改变转移。$\square$

复杂度

满分算法对每个测试用例的时间复杂度为 $O(nk^2)$，空间复杂度为 $O(k^2)$。