← 返回题目列表

AtCoder · abc413_e

H. 反转 2^i

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你一个排列 P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).

您可以执行以下操作任意次数(可能为零):

  • 选择非负整数 a,b 满意 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N},并反转 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}。在这里,倒车 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} 表示同时更换 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} 与 P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.

找到字典顺序最小的排列 重复操作即可得到 P 。

你被给予 T 测试用例,因此找到每个用例的答案。

约束

  • 1 \leq T \leq 10^{5}
  • 1 \leq N \leq 18
  • P 是一个排列 (1,2,3,\ldots,2^{N}).
  • 对于每个输入文件,总和 2^N 所有测试用例最多 3 \times 10^{5}.
  • 所有输入值均为整数。

输入

输入由标准输入给出,格式如下:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i 代表 i-第一个测试用例,以以下格式给出:

N
P_0 P_1 \ldots P_{2^N-1}

输出

输出 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

4
1
1 2
2
1 3 4 2
2
2 3 4 1
3
8 3 4 2 1 5 7 6

示例输出 1

1 2
1 3 2 4
1 4 2 3
1 5 6 7 2 4 3 8

在第一个测试用例中,当不执行任何操作时 P, P=(1,2)。这是字典顺序上最小的排列。因此,答案是 (1,2).

在第二个测试用例中,当我们执行操作时 a=1,b=1, P 变为 (1,3,2,4)。无论我们执行多少操作 P,我们无法获得按字典顺序小于的排列 (1,3,2,4)。因此,答案是 (1,3,2,4).

在第三个测试用例中,通过按以下顺序执行操作,我们可以得到 P=(1,4,2,3):

  • 执行操作 a=0,b=1. P 变为 (3,2,4,1).
  • 执行操作 a=0,b=2. P 变为 (1,4,2,3).

无论我们执行多少次操作 P,我们无法获得按字典顺序小于的排列 (1,4,2,3)。因此,答案是 (1,4,2,3).