本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-04 10:09:03

题解里怎么都用 trie，让我来篇不用 trie 的题解！

我们先找一下规律，容易发现只要知道了第一个数，那么后面的数就全知道了，现在的问题就是让 $0- n-1$ 中的数全部出现。

我们设构造的数组的第一个为 $k$。 那么：

$b_1=k, b_2=a_1 \oplus b_1,b_3=a_1 \oplus a_2\oplus b_1$.....

以此类推，所以我们发现 $b$ 中的所有数都可以表示为一个数异或上 $b_1$ 的形式。

我们发现直接考虑不太好做，于是我们考虑拆位。

如果说 $0- n-1$ 这些数中第 $j$ 位上有 $sum$ 个 1 的话，我们就必须得让 $b$ 数组最终也有 $sum$ 个 1。所以我们统计一下 $a_1,a_1 \oplus a_2,a_1 \oplus a_2 \oplus a_3...$ 中第j位上有多少个 1，如果说有 1 的个数恰好等于 $sum$，那么第一个数这位上是要填 0 的，因为 $0 \oplus 1=1$，否则就必须填1。

至于为啥有解的话我也不太会证，本来想写个判断的，结果看到题目中没说无解输出什么，就直接输出了。

参考代码实现（写的有点丑）：

#include <bits\/stdc++.h>
#define N 500005
#define M 13000005
#define mod 998244353
#define lowbit(x) (x&-x)
#define ls(x) llll[x]
#define rs(x) rrrr[x]
#define ll long long
\/\/#define int long long 
using namespace std;
int t,n;
int a[N],qian[N],b[N];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;++i){\/\/让i从2开始方便一些
		cin>>a[i];
		qian[i]=qian[i-1]^a[i];\/\/处理前缀异或
	}	
	for(int j=0;j<=21;++j){
		if((1<<j)>=n)continue;
		int sum=0;
		for(int i=0;i<n;++i){
			if((i>>j)&1)++sum;
		}
      \/\/统计有应该有多少个1
		int sum1=0,sum2=0;
		for(int i=2;i<=n;++i){
			if((qian[i]>>j)&1)++sum1;
			else ++sum2;
		}
		if(sum1==sum){\/\/如果说1的个数和要求的一样
        ;\/\/那么这位填0
		}
		else
			b[1]+=(1<<j);\/\/否则填1
	}
	ll lst=b[1];
	for(int i=1;i<=n;++i){
		cout<<(lst^a[i])<<' ';\/\/最后已知第一位直接求出每一位
		lst^=a[i];
	}
	return 0;
}
\/*
k a1^k
a1^a2^k
a1^a2^a3^k
*\/