题目描述

企鹅是一种文明的生物，它们用排列进行交流。Blackslex 作为企鹅研究者，必须研究它们的交流方式。

对于一个给定的整数 $n$，考虑 $[0, 1, \ldots, 2^n - 1]$ 的所有排列 $^{\text{∗}}$ $p$。定义

$$S(p) = \sum_{i=0}^{2^n-1} \operatorname{popcount}\bigl(p_0 \ \&\ p_1\ \&\ \cdots \ \&\ p_i\bigr),$$

其中 $\operatorname{popcount}(z)$ 表示 $z$ 的二进制表示中 $1$ 的个数（例如，$\operatorname{popcount}(5)=2$，因为 $5=101_2$ 二进制表示有两个 $1$），$\&$ 表示按位与运算。

如果一个排列使得 $S(p)$ 最大，则称其为“神圣排列”。请找到字典序最小$^{\text{†}}$的神圣排列。

$^{\text{∗}}$ 一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（因为 $2$ 出现了两次），$[1,3,4]$ 也不是（因为 $n=3$，但数组中有 $4$）。

$^{\text{†}}$ 两个等长数组 $a$ 和 $b$ 比较字典序时，如果在第一个不同的位置，$a$ 的该元素小于 $b$ 的对应元素，则称 $a$ 的字典序小于 $b$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 16$），表示测试用例的个数。

每个测试用例包含一个整数 $n$（$1 \le n \le 16$）。

保证所有测试用例中 $2^n$ 的和不超过 $2^{16}$。

输出格式

对于每个测试用例，输出 $2^n$ 个整数 $p_0, p_1, \ldots, p_{2^n-1}$，即所求的排列。

样例

2
1
2

1 0 
3 1 0 2

样例说明

对于第一个测试用例，有两种可能的排列。

• $p = [0, 1]$，$S(p) = 0$
• $p = [1, 0]$，$S(p) = 1$

对于第二个测试用例，$S([3, 1, 0, 2]) = 3$ 是神圣排列。还有其他神圣排列，例如 $p = [3, 2, 0, 1]$，但这些不是字典序最小的。

由 ChatGPT 5 翻译

来源

Codeforces 2179D，英文题名 Blackslex and Penguin Civilization。