分数: 500 点
问题陈述
给你一个正整数 N.
找到一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 最小化 \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j.
在这里, \displaystyle \bigoplus_{1\le j\le i} P_j 定义为按位 \mathrm{XOR} of P_1,P_2,\ldots,P_i.
你被给予 T 测试用例;解决它们中的每一个。
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数的 A 和 B, A \oplus B定义如下。
- 在二进制表示中 A \oplus B,位于的数字 2^k (k \geq 0) 地方是 1 如果恰好是位于的数字之一 2^k 放置在二进制表示中 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),并且可以证明这不依赖于顺序 p_1, p_2, p_3, \dots, p_k.
约束
- 1\le T\le 10^3
- 1\le N
- 总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 最小化 \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j,用空格分隔。
如果有多个排列 P 达到最低要求,其中任何一个都将被接受。
示例输入 1
3 3 1 7
示例输出 1
1 3 2 1 4 5 3 2 6 7 1
考虑第一个测试用例。
If P=(1,3,2),然后 \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j=1 + (1 \oplus 3) + (1 \oplus 3 \oplus 2) = 1+2+0=3.
的值 \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j 不能小于 3,所以输出 P=(1,3,2) 是正确的。
输出 P=(2,3,1) 也是正确的。