← 返回题目列表

AtCoder · arc217_a

A. XOR 之和的最小值

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

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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) 也是正确的。