# 题解：地牢房间的行为等价

Codex（GPT-6）：将障碍行为建模为确定有限自动机，应用 Hopcroft 划分细化，给出适配本题的实现与证明。自动机最小化方法不归为模型原创。

## 从试验到自动机

增加吸收状态0，所有方向都从0回到0。把房间视为接受状态、0视为不接受状态。这样，执行完一个指令串仍在房间中，当且仅当没有遇到障碍。题目等价关系正是这台自动机的状态等价关系。

从两个块 $\{0\}$ 和 $\{1,\ldots,n\}$ 开始。若某块内的状态在指令 $j$ 下转移到不同块，就把它们分开。稳定划分满足：同块状态的每种指令都转向同一个块。

稳定划分中，同块状态对长度为零的试验结果相同；对非空指令串，第一步仍进入同一块，对剩余长度归纳可知试验结果相同。反过来，真正等价的状态从不会被分开：初始接受性相同，而任何一个等价类在同一指令下的后继仍然等价。因此最后得到的正是等价类，减去障碍所在的一类即可。

## 用小块细化

维护待处理块队列。取出一个块 $A$ ，对每个指令 $j$ ，沿反向边找出

$$X=\{u:\ a_{u,j}\in A\}$$

每个与 $X$ 相交的块 $Y$ 都分成 $Y\cap X$ 与 $Y\setminus X$ ，空部分不产生新块。

初始只需要将障碍块入队：整台自动机转移完整，另一块是它的补集，按补集细分不会提供额外区分。后续保留较大一半的块编号，较小一半分配新编号并入队。如果较大一半对应的旧编号还在队列中，它仍将被处理；若旧块已经处理过，补上较小一半就足够，因为一个集合与其中一半的归属已确定后，另一半的归属也就确定了。

一个块可能在处理不同指令期间被再次分割。因此程序在出队时复制其当前成员作为本轮快照；本轮所有指令都对该快照求前驱，保证处理的是同一个集合。

## 只移动实际命中的状态

用一个状态排列及其逆排列表示所有块，每个块占据连续区间。遍历 $X$ 时，把命中的状态交换到所属块区间的前部，记录各块命中数量。之后只为较小一半更新块编号；移动的数量不超过已经找到的前驱数量，不扫描整个大块。

每个状态在进入新的待处理小块时，所属块大小至少减半；同一个保留编号最多出队一次。因此每个状态参与反向边扫描的次数为 $O(\log(n+1))$ .每个状态每种指令只有一条出边，在固定指令的一轮扫描中不会重复命中。

总时间 $O(nk\log(n+1))$ ，空间 $O(nk+n)$ .数据范围中的乘积限制控制反向边数组大小。逐轮重算全部转移签名的方法在长链上需要线性轮数，适合小规模独立核验；生成器包含该核验实现，完整标程使用小块细化。

见[标准程序](std.cpp)、[测试说明](tests/README.md)和[性能记录](../../../docs/benchmark-R37.json)。