← 返回题目列表

Codeforces · 2189/C1

C1. XOR 便利(简单版)

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

这是 简单 版本问题。版本之间的区别在于,在这个版本中,$$$2 \le i \le n-1$$$。请注意,正确的解决方案是 硬 版本不一定是正确的解决方案 简单 版本。

给定一个自然数$$$n$$$。找到长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$,使得对于每个 $$$i$$$ ($$$\style{color:red}{2 \le i \le n-1}$$$) 都存在一个 $$$j$$$ ($$$\style{color:red}{i \le j \le n}$$$) 使得 $$$p_i = p_j \oplus i$$$ $$$^{\text{†}}$$$。

可以证明,在问题的约束下,至少存在一种合适的排列$$$p$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{†}}$$$$$$\oplus$$$ 表示按位异或运算。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 排列的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ — 排列 $$$p$$$。

如果有多个解,则可以输出其中任何一个。

示例

输入
复制

2
3
6

输出
复制

2 1 3
3 6 2 5 1 4

注意

在第一个测试用例中,排列 $$$p = [2,1,3]$$$ 是合适的,因为 $$$p_2 = 1$$$ 和 $$$p_3 \o​​plus 2 = 1$$$。

在第二个测试用例中,排列 $$$p = [3,6,2,5,1,4]$$$ 是合适的,如下所示:

  • $$$p_2 = 6 = 4 \oplus 2 = p_6 \oplus 2$$$
  • $$$p_3 = 2 = 1 \oplus 3 = p_5 \oplus 3$$$
  • $$$p_4 = 5 = 1 \oplus 4 = p_5 \oplus 4$$$
  • $$$p_5 = 1 = 4 \oplus 5 = p_6 \oplus 5$$$