菜王的 blog

对于一个指令序列，我们设 $f(x)$（$1 \le x \le m + 1$）表示机器人从 $x$ 位置出发执行一轮后到达的位置。特别地，如果在执行的过程中坠落，那么 $f(x) = m + 1$。那么指令序列需要满足的要求就是 $f^\infty(x) \le m$。

考虑 $f(x)$ 的一些性质。首先 $f(x)$ 是单调不降的，这个是非常显然的。然后我们可以发现，设 $g(x) = f(x) - x$（$1 \le x \le m$），也就是执行一轮后位置的增量，那么 $g(x)$ 是单调不增的。这是因为，初始位置越靠左，被峭壁挡住的次数就越多，并且如果指令序列合法，那么一定存在至少一个 $x$ 使得 $g(x) = 0$。那么，$f(x)$ 一直迭代下去一定会在这个点上收敛。

那么我们考虑将一个操作序列在限制最严的那一轮统计。

1. $f(x) < x$：对于这样的操作序列，显然只有第一轮的限制是最严的，所以我们只需要对于第一轮 DP 即可。
2. $f(x) \ge x$：对于这样的操作序列，到了收敛的时候的限制是最严的，所以我们在收敛的那一轮统计这种操作序列。具体地，假设一个操作序列的 $f(k) = k$，那么对于每个 $s < k$ 的起始点，它都会收敛在 $k$ 位置。但是有多个合法的 $k$ 时这样会算重，那么我们只在最小的那个 $k$ 处统计，就是相当于在前面的基础上强制要求操作时必须要走到过 $1$ 位置。最后将 $f(s) = s$ 的情况算上即可。

那么设 $f_{i, j, 0/1}$ 表示一轮中执行了前 $i$ 个操作，目前在位置 $j$，是否走到过位置 $1$ 的方案数。对于每个起始点分别 DP 一次即可做到 $\mathcal O(nm^2)$。

实际上还有结论：对于任意一个 $x$ 与任意一个指令序列，若 $f(x) \ge x$ 则 $f(f(x)) = f(x)$。证明在这里略去。但是上述解法并不依赖这个结论。