题解：SP10077 ROUTING - Routing

ZnPdCo · 2024-12-19 22:09:39 · 题解

一个 n-Benes 网络由交换器组成。一个交换器有两个输入端 X, Y 和两个输出端 X', Y'。如果交换器处在关闭状态，那么 X 端的信号就直接被发送到 X'，Y 端的信号发送到 Y'；否则，如果交换器打开，那么 X 端的信号就发送到 Y'，Y 端的信号就发送到 X'。

而 Benes 网络是递归定义的。1-Benes 网络就是一个单纯的交换器，而 n-Benes 网络的第一排是 2^{n-1} 个交换器，也就有 2^n 个输入端和输出端，从左到右用 n 位二进制数表示。第一排的输出端 k，与第二段的输入端 k \gg 1 相连，其中 \gg 表示循环右移，即最后一位移位之后变成第一位。在第一排后面放置两个 (n-1)-Benes 网络。在最后一排再放置 2^{n-1} 个交换器，倒数第二排的输出端 k 连向最后一排的输入端 k \ll 1，其中 \ll 表示循环左移，亦即前两排之间输入输出端口变换的逆变换。一个 3-Benes 网络如下图所示。

通过恰当地设置 Benes 网络中的交换器，可以实现整个网络输入端与输出端的变换。上图的右侧实现了输出端 0 \sim 7 分别与输入端 3, 7, 4, 0, 2, 6, 1, 5 相接的 3-Benes 网络。

你的任务是，对于给定的 n-Benes 网络与变换，求一个满足要求的交换器配置。

输入文件包含多个测试数据。每个测试数据包含两行，第一行是一个整数 n，表示你要处理的是 n-Benes 网络；第二行包含 0 到 2^n - 1 的一个排列，排列的第 k 个数 a_k 表示输出端 k 需要与输入端 a_k 相连。

输入文件以 0 结尾。

对于每个测试数据，打印 2n + 1 行 2^{n - 1} 位二进制数，表示配置好的 n-Benes 网络。二进制位 1 表示对应位置的交换器是打开的，0 表示交换器是关闭的。

保证有解，如有多解，打印字典序最小的。

在每个答案之后打印一个空行。