# 交换之后的复原 — 补充题解

本方案应用 [Evans、Huang 与 Nguyen 的联合环构造](https://arxiv.org/abs/1204.6086)。Codex（GPT-6）适配身体到思想的环方向并实现验证，程序见 [alternative.cpp](alternative.cpp)。

## 联合处理

沿用[标准题解](solution.zh.md)的环方向。将非平凡环记为 $C_1,\ldots,C_c$ ，每环按 $a_1,\ldots,a_t$ 存储，定义其轮转序列为 $a_2,\ldots,a_t,a_1$ .若没有非平凡环，输出零。

否则依次执行：

1. 按 $C_c,\ldots,C_2$ 的顺序，交换 $y$ 与各环首点。
2. 对首环，先交换 $(x,a_1)$ ，再让 $y$ 按轮转序列逐点交换，最后交换 $(x,a_2)$ .
3. 按 $C_2,\ldots,C_c$ 的顺序，让 $x$ 与各环的轮转序列逐点交换。
4. 交换 $(x,y)$ .

## 状态不变量与次数

步骤 1 将后续环首点中的思想接成链。步骤 2 复原首环，使 $y$ 拿回 $x$ 的思想，$x$ 拿到下一环第二个身体的正确思想。步骤 3 每处理一环就顺次放回它的思想，并取出下一环所需思想；最后 $x$ 持有 $y$ 的思想。步骤 4 完成复原。各辅助与普通身体对至多使用一次。

若非平凡环覆盖 $s$ 个身体，次数为 $s+c+2\le2N+1$ ，时间 $O(N+M)$ 、空间 $O(N)$ .与逐环法在一、二个环时次数相同，更多环时更少；需要减少输出时推荐此方案。题目允许其他未使用的普通身体对，因此这里不宣称它对每份具体历史都全局最优。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R33.json)