题解：地牢房间的行为等价¶
Codex（GPT-6）：将障碍行为建模为确定有限自动机，应用 Hopcroft 划分细化，给出适配本题的实现与证明。自动机最小化方法不归为模型原创。
从试验到自动机¶
增加吸收状态0，所有方向都从0回到0。把房间视为接受状态、0视为不接受状态。这样，执行完一个指令串仍在房间中，当且仅当没有遇到障碍。题目等价关系正是这台自动机的状态等价关系。
从两个块 \(\{0\}\) 和 \(\{1,\ldots,n\}\) 开始。若某块内的状态在指令 \(j\) 下转移到不同块，就把它们分开。稳定划分满足：同块状态的每种指令都转向同一个块。
稳定划分中，同块状态对长度为零的试验结果相同；对非空指令串，第一步仍进入同一块，对剩余长度归纳可知试验结果相同。反过来，真正等价的状态从不会被分开：初始接受性相同，而任何一个等价类在同一指令下的后继仍然等价。因此最后得到的正是等价类，减去障碍所在的一类即可。
用小块细化¶
维护待处理块队列。取出一个块 \(A\) ，对每个指令 \(j\) ，沿反向边找出
每个与 \(X\) 相交的块 \(Y\) 都分成 \(Y\cap X\) 与 \(Y\setminus X\) ，空部分不产生新块。
初始只需要将障碍块入队：整台自动机转移完整，另一块是它的补集，按补集细分不会提供额外区分。后续保留较大一半的块编号，较小一半分配新编号并入队。如果较大一半对应的旧编号还在队列中，它仍将被处理；若旧块已经处理过，补上较小一半就足够，因为一个集合与其中一半的归属已确定后，另一半的归属也就确定了。
一个块可能在处理不同指令期间被再次分割。因此程序在出队时复制其当前成员作为本轮快照；本轮所有指令都对该快照求前驱，保证处理的是同一个集合。
只移动实际命中的状态¶
用一个状态排列及其逆排列表示所有块，每个块占据连续区间。遍历 \(X\) 时，把命中的状态交换到所属块区间的前部，记录各块命中数量。之后只为较小一半更新块编号；移动的数量不超过已经找到的前驱数量，不扫描整个大块。
每个状态在进入新的待处理小块时，所属块大小至少减半；同一个保留编号最多出队一次。因此每个状态参与反向边扫描的次数为 \(O(\log(n+1))\) .每个状态每种指令只有一条出边，在固定指令的一轮扫描中不会重复命中。
总时间 \(O(nk\log(n+1))\) ，空间 \(O(nk+n)\) .数据范围中的乘积限制控制反向边数组大小。逐轮重算全部转移签名的方法在长链上需要线性轮数，适合小规模独立核验；生成器包含该核验实现，完整标程使用小块细化。