← 返回题目列表

Codeforces · 2179/D

D. Blackslex 和企鹅文明

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

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

对于给定的整数 $$$n$$$,考虑数组 $$$[0, 1, \ldots, 2^n - 1]$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$。定义 $$S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$ 其中 $$$\operatorname{popcount}(z)$$$ 是二进制表示中 $$$1$$$ 位的数量$$$z$$$(例如,$$$\operatorname{popcount}(5) = 2$$$,因为$$$5 = 101_2$$$ 在二进制表示中有两个 $$$1$$$ 位),$$$\&$$$ 表示按位 AND 运算。 。

考虑排列 神圣 如果最大化$$$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$$$,例如 $$$p = [3, 2, 0, 1]$$$,但这些排列在字典顺序上并不是最小的。