题解

思路

一个数组 $a$ 不合法，当且仅当所有从 $b_0$ 出发、每步上下移动一格且不越过 $-1$ 的路径，都在某一时刻撞到禁点 $(i,a_i)$。可以把计数转化为一维随机游走的网格路径计数。

做法

子任务 1：枚举数组

枚举全部 $m^n$ 个数组 $a$。对每个数组维护当前可达的非负高度集合，转移到相邻高度并删去等于 $a_i$ 的状态。末尾仍有可达高度则该数组合法。

子任务 2：高度动态规划

若路径在某一时刻到达高度 $m$，此后可以一直向上走，永远不会与取值不超过 $m$ 的 $a_i$ 相等。因此只需维护高度 $0,1,\ldots,m-1$。

令 $dp_{i,h}$ 表示处理前 $i$ 位后仍未到达高度 $m$、当前位于高度 $h$ 的相关计数。向上转移会有 $m-1$ 种不冲突的禁值选择，向下转移则有一种对应贡献；第一次到达 $m$ 后，剩余位置可任取。这样可在 $O(nm)$ 时间内求解。

满分算法：反射原理

把上下移动数分别看作网格路径的横、纵步。对“首次撞到下边界 $-1$”和“首次到达上边界 $m$”进行容斥。连续反射一条越界路径后，终点会按周期 $2(m+1)$ 平移，因此只需枚举 $O(n/(m+1))$ 个反射像。

对每个反射像，可达终点区间对应一段二项式系数：走 $i$ 次上步、$n-i$ 次下步的路径数为 $\binom ni$。把该反射像的系数记录到差分数组中，再利用

线性扫过全部 $i$，即可得到答案。实现中还使用另一套 $O(n\sqrt n)$ 混合算法作为独立复核：当 $m\le\sqrt n$ 时运行高度 DP，否则直接枚举反射像。

若 $b_0\ge m$，单调向上路径从第一步起就高于所有 $a_i$，所以全部 $m^n$ 个数组均合法。

复杂度

枚举算法为 $O(nm^n)$；中层算法为 $O(nm)$、空间 $O(m)$；满分算法为 $O(n+n/(m+1))$、空间 $O(n)$。独立复核算法为 $O(n\sqrt n)$。

正确性证明

枚举算法直接检查定义。高度 DP 对每条未越过上边界的路径及与其不冲突的禁值选择逐步计数，并在首次到达 $m$ 时一次性加入所有后缀选择，因此无重不漏。反射原理在“首次碰到边界”处建立越界路径与反射路径的一一对应；交替反射上下边界得到符号交替的全部容斥项。差分数组只是在终点范围上批量加入相同权重，不改变每个二项式项的系数。故满分算法与高度 DP 计数相同，输出恰为合法数组数量。