CF1722G Even-Odd XOR

题意

给定一个正整数 \(n\)，请你找出一个长度为 \(n\) 数组 \(a\)，满足数组是由互不相同的非负且小于 \(2^{31}\) 的整数组成，并且该数组中奇数项上元素的异或值与偶数项上元素的异或值要相等。

思路

根据异或的交换律，可以发现：奇偶位异或值相等，那么全局异或值位0，如下：

\((a_1\oplus a_3 \oplus ... a_{2k+1})\oplus(a_2\oplus a_4\oplus ... a_{2k})=0\)

根据的就是\(a\oplus a=0\)

所以，假如已知\(1,2,...,n-1\)，那么\(n\)就一定能被求出来，使得全局异或为\(0\)

但是这种情况下很容易出现重复，所以可以这么构造：\(1,2,...,n-3,2^{23},2^{24}\)，最后一个数就是前面所有数的异或值，这样全局异或还是\(0\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,num;
void run()
{
	cin>>n;num=0;
	for(int i=1;i<=n-3;i++)
	{
		cout<<i<<" ";
		num^=i;
	}
	cout<<(1<<23)<<" "<<(1<<24)<<" "<<(num^(1<<23)^(1<<24))<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run(); 
}