CF1722G - Even-Odd XOR
G. Even-Odd XOR
Given an integer \(n\), find any array \(a\) of \(n\) distinct nonnegative integers less than \(2^{31}\) such that the bitwise XOR of the elements on odd indicts equals the bitwise XOR of the elements on even indicts.
Input
The first line of the input contains an integer \(t\) \((1≤t≤629)\) — the number of test cases.
Then \(t\) lines follow, each containing a single integer \(n\) \((3≤n≤2⋅10^5)\) — the length of the array.
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2⋅10^5\).
Output
For each test case, output one line containing \(n\) distinct integers that satisfy the conditions.
If there are multiple answers, you can output any of them.
Example
Input
7
8
3
4
5
6
7
9
Output
4 2 1 5 0 6 7 3
2 1 3
2 1 3 0
2 0 4 5 3
4 1 2 12 3 8
1 2 3 4 5 6 7
8 2 3 7 4 0 5 6 9
Note
In the first test case the XOR on odd indicts is \(4⊕1⊕0⊕7=2\) and the XOR on even indicts is \(2⊕5⊕6⊕3=2\).
题面翻译
给一个整型 \(n\)，让你寻找一个由 \(n\) 个互不相同的非负整型组成的数组 \(a\)，使得数组 \(a\) 中奇数下标的数和偶数下标的数分别进行 XOR 运算结果相同。
输入
第一行是一个整型 \(t\) \((1≤t≤629)\)， 代表测试点的个数。
接下来 \(t\) 行，每一行有一个整型 \(n\) \((3≤n≤2⋅10^5)\) ，代表数组大小。
数据保证 \(n\) 的总和不超过 \(2⋅10^5\).
输出
对于每个测试点，输出 \(n\) 个满足题意的互不相同的整型。
如果有很多解，输出其中任意一个。
样例
输入
7
8
3
4
5
6
7
9
输出
4 2 1 5 0 6 7 3
2 1 3
2 1 3 0
2 0 4 5 3
4 1 2 12 3 8
1 2 3 4 5 6 7
8 2 3 7 4 0 5 6 9
补充
第一个测试点中，奇数下标的数 XOR 的结果是 \(4⊕1⊕0⊕7=2\) ，偶数下标的数 XOR 的结果是 \(2⊕5⊕6⊕3=2\)。
官方题解
There are a lot of solutions to this problem. Here I will describe one of them.
First, we observe that having the XOR of even indexed numbers and odd indexed numbers equal is equivalent to having the XOR of all the elements equal to \(0\). Let’s note with \(a\) the XOR of all odd indexed numbers and \(b\) the XOR of all even indexed numbers. Notice that the XOR of all the array equals \(0\) if and only if \(a = b\).
So how do we generate such an array with XOR of all elements \(0\)? Our first instinct might be to arbitrarily generate the first \(n-1\) numbers, then set the last element as the XOR of the first \(n-1\), ensuring that the total XOR is \(0\). However, we might have problems with the condition that all elements must be distinct. Let’s arbitrarily set the first \(n-2\) so that they don’t have the highest bit(\(2^{30}\)) set, and then the \(n-1\)-th number can be just \(2^{30}\). The last number can be the XOR of the first \(n-2\) XOR the \(n-1\)-th number; you will be sure that the last number has not occurred in the first \(n-2\) elements because they don’t have the highest bit set while the last number must have the highest bit set. But how do we know that the \(n-1\)-th number and the \(n\)-th number will not be equal? This occurs only if the total XOR of the first \(n-2\) numbers equals \(0\). To fix this, we can just choose a different arbitrary number in one of the \(n-2\) spots.
For example, my solution checks if the XOR of the numbers \(0,1,2...,n-4,n-3\) is \(0\), great! We can use the simple solution without any changes. However, if the XOR is \(0\) I use the numbers \(0,1,2...,n-4,n-3,n-2\) in their place. These two sequences have different XORs, so it ensures that one of them always works.
官方题解翻译
这道题有很多种解法，这里分享其中一个。
首先需要知道，如果我们能得到一个数组，让奇数下标的数和偶数下标的数分别进行 XOR 的运算结果相同，那么所有数 XOR 的结果必为 \(0\)。我们用 \(a\) 来表示所有奇数下标数的XOR，用 \(b\) 来表示偶数下标数的 XOR，那么当且仅当 \(a = b\) 时，所有数字的 XOR 结果为 \(0\)。
问题是，要怎样生成一个数组，让它里面所有的数 XOR 后结果为 \(0\) 呢？我们的第一反应也许是生成一个含有前面 \(n-1\) 个数字的数组，然后把最后一个数定为前面 \(n-1\) 个数的 XOR，以此来确保最后的结果为 \(0\)。但考虑到每个数字各不相同的条件，这个方法会遇到问题。进一步想，我们可以把前 \(n-2\) 个数先定下来，让它们都没有第 \(31\) 位的二进制，那么我们就能把第 \(n-1\) 个数直接设置成 \(2^{30}\)，最后一个数也就能设置成前面所有数的 XOR，这样可以保证最后一个数在前 \(n-2\) 个数中完全没有出现过，因为在这之前的所有数都不存在第 \(31\) 位的二进制。接下来怎么保证最后两个数不同呢？事实上，只有前 \(n-2\) 个数的 XOR 为 \(0\) 的时候，这种情况才会出现。我们只需要在前 \(n-2\) 个数中随便换个数字就可以了。
比如，如果 \(0,1,2...,n-4,n-3\) 的运算结果不是 \(0\)，那挺好，我们就可以直接用最简单的方法得出答案。但是，如果运算结果是 \(0\)，那我们就把其中一个数换成 \(n-2\)，这两个序列总是有着不同的运算结果，所以它们可以总是保证结果不为 \(0\)。
个人 AC 代码
#include <bits/stdc++.h>
using namespace std;
int t, n;
int a = 1<<18; // 其实19位就够了
int check; // 存前n-2个数的XOR结果
bool f; // 用来记录数组{0,1,2,3...,n-4,n-3}的XOR结果是不是0，不是0为真，是0为假
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while(t--)
{
cin >> n;
check = 0;
for(int i = 1; i < n-3; i++) check ^= i;
if(check^n-3 == 0) check ^= n-2, f = false;
else check ^= n-3, f = true;
for(int i = 0; i < n-3; i++) cout << i << ' ';
if(f) cout << n-3 << ' ';
else cout << n-2 << ' ';
cout << a << ' ' << (a^check) << '\n';
}
return 0;
}