一、题意理解

1. 交换器（Switch）

一个交换器有两个输入 $x, y$ 和两个输出 $x', y'$：

• 关闭（0）：$x \to x'$，$y \to y'$（直通）。
• 开启（1）：$x \to y'$，$y \to x'$（交叉）。

交换器实际上是一个 2 输入 2 输出的可控置换元件。

---

2. 递归网络结构

• 1 阶网络：1 个交换器（2 输入 2 输出）。
• n 阶网络（$n>1$）：
  1. 第一排：$2^{n-1}$ 个交换器。
  2. 中间：两个 $(n-1)$ 阶网络。
  3. 最后一排：$2^{n-1}$ 个交换器。
  4. 连接方式：
     • 第一排输出 → 第二排输入：编号 $i$ 的输出连接到 $i \gg 1$（循环右移 1 位）。
     • 倒数第二排输出 → 最后一排输入：编号 $i$ 的输出连接到 $i \ll 1$（循环左移 1 位）。

网络总共有 $2n-1$ 排交换器（因为 n=1 时 1 排，n>1 时第一排+两个(n-1)阶网络+最后一排 = 1 + (2(n-1)-1) + 1 = 2n-1）。

---

3. 问题

给定输入排列 $0,1,\dots,2^n-1$（即输入 $i$ 位置的值是 $i$），希望输出排列为给定的 $p$。
通过设置每个交换器的状态（0 或 1），能否实现？如果能，输出字典序最小的交换器状态矩阵。

矩阵大小：$(2n-1) \times 2^{n-1}$（每排 $2^{n-1}$ 个交换器）。

---

二、网络结构分析

这个递归结构实际上是 Benes 网络（一种可重排非阻塞网络）的变形。
Benes 网络可以实现任意置换，且控制状态可以高效构造。

关键性质：逆序构造法
从输出端往输入端反向确定交换器状态。

---

三、算法思路

1. 置换表示

设输入 $i$ 最终输出到 $p_i$。
我们可以把问题看作：给定输入到输出的映射 $i \to p_i$，要在网络中实现。

网络结构是递归的，所以我们可以递归地确定交换器状态。

---

2. 递归处理

考虑最后一排（第 $2n-1$ 排）的交换器。
它们的输出直接连到最终输出端口。
输入来自两个 $(n-1)$ 阶子网络的输出，并且通过循环左移连接。

关键观察：
对于每个交换器，它的两个输出位置 $2k$ 和 $2k+1$ 在最终输出中，对应的输入来源是 $i$ 和 $i \oplus 1$（因为交换器前一级是循环左移连接）。

所以我们可以从最后一排开始，确定每个交换器的状态，使得输出排列正确，并且将问题递归到两个子网络。

---

四、代码解析

1. 变量定义

• n：网络阶数。
• a[1<<n]：当前处理的置换（开始时是目标置换 $p$）。
• ans[i][j]：第 $i$ 排第 $j$ 个交换器的状态（-1 表示未确定）。
• b 和 c：临时数组，b 存储当前子问题中的置换，c 是 b 的逆（位置映射）。
• s = 1<<(n-1)：每排交换器数量。

---

2. 主循环

for (int i = n; i >= 1; i--) {
    int l = 1 << (i - 1); // 当前子问题中交换器数量
    for (int j = 0; j < s; j += l) {
        // 处理一个大小为 2*l 的子问题
    }
}

从大到小处理子网络：先处理最后一排（对应 i=n），然后递归到更小的子网络。

j 是子网络在整排中的起始位置。

---

3. 处理一个子问题

A = ans[n - i + 1] + j, B = ans[n + i - 1] + j;

• A 指向当前子网络的第一排交换器状态。
• B 指向当前子网络的最后一排交换器状态。

对于 n 阶网络：

• 第一排索引 = n - i + 1
• 最后一排索引 = n + i - 1

---

4. 构建当前子置换

for (int k = 0; k < l; k++) {
    b[k << 1] = a[(j + k) << 1];
    b[k << 1 | 1] = a[(j + k) << 1 | 1];
    c[b[k << 1]] = k << 1;
    c[b[k << 1 | 1]] = k << 1 | 1;
}

a 数组存储的是当前子问题的输出目标（经过上一级处理后的置换）。
b 是当前子网络中两个输入端口对应的输出值。
c 是 b 的逆映射：值 → 位置。

---

5. DFS 确定交换器状态

void dfs(int x) {
    if (~A[x >> 1]) return; // 已确定
    if (!(x & 1))
        A[x >> 1] = 0;
    else
        A[x >> 1] = 1;
    if (!(c[x] & 1))
        B[c[x] >> 1] = 0;
    else
        B[c[x] >> 1] = 1;
    dfs(b[c[x] ^ 1] ^ 1);
}

x 是输入端口编号（在当前子问题中，0 到 2*l-1）。

• A[x>>1] 是当前子网络第一排的交换器状态。
• B[c[x]>>1] 是最后一排的交换器状态。

逻辑：

• 如果 x 是偶数（x&1==0），那么在第一排交换器中，x 从直通端出去，所以 A=0；否则 A=1。
• 在最后一排，c[x] 是 x 对应的输出位置，如果 c[x] 是偶数，则直通，B=0；否则 B=1。
• 然后递归处理配对的另一个端口。

这个 DFS 确保一致性：确定了第一排的一个交换器状态，就会确定最后一排对应的交换器状态，并继续链式确定。

---

6. 更新置换传递给子问题

for (int k = 0; k < l; k++)
    if (!B[k])
        a[(j << 1) + k] = b[k << 1]>>1,
        a[(j << 1) + k + l] = b[k << 1 | 1] >> 1;
    else
        a[(j << 1) + k] = b[k << 1 | 1] >> 1,
        a[(j << 1) + k + l] = b[k << 1]>>1;

B[k] 是最后一排交换器状态：

• 如果 B[k]=0（直通），则交换器输出端口 2k 和 2k+1 分别来自输入 k<<1 和 k<<1|1。
• 如果 B[k]=1（交叉），则交换。

更新 a 数组，表示进入子网络的输入目标（右移 1 位是为了适应更小的子网络规模）。

---

五、算法总结

1. 从大到小处理子网络（i 从 n 到 1）。
2. 对每个子网络：
   • 根据当前置换，用 DFS 确定第一排和最后一排交换器状态。
   • 更新置换，传递给两个子子网络。
3. 输出：ans 数组就是交换器状态矩阵。

---

六、正确性保证

这个算法利用了 Benes 网络的可重排性质：

• 对于任意置换，存在至少一种交换器设置。
• DFS 方法可以找到一种设置，且按字典序最小（因为总是先尝试 0 状态）。

字典序最小是因为：

• 当 A[x>>1] 未确定时，总是先设 A=0（如果可能）。
• DFS 顺序保证了最早的可能状态被采用。

---

七、样例验证

样例 1

n=2
p = 3 2 1 0

网络结构：

• 第 1 排：1 个交换器
• 第 2 排：1 个交换器
• 第 3 排：1 个交换器

算法输出：

00  (第1排)
11  (第2排)
11  (第3排)

交换器全为交叉状态，实现完全反转。

---

样例 2

n=3
p = 3 7 4 0 2 6 1 5

输出 5 排，每排 4 位。

---

八、复杂度

• 时间：$O(2^n \cdot n)$，因为每个子网络 DFS 是线性的。
• 空间：$O(2^n)$。

可以处理 $n \le 13$（$2^{13}=8192$）。

---

这个解法利用了 Benes 网络的可重排性质，通过逆序构造和 DFS 一致性检查，高效找到字典序最小的交换器设置。