https://ac.nowcoder.com/acm/contest/120563/I

正好复习一下线性基。

给定一个数组，长度为，设数组中所有数的二进制最高位为，那么该数组中的数互相异或的结果最多只有种，显然大多数情况下。这给我们启发：其实我们可以在上挑个数，使原数组所有可能的异或结果都能通过这个数互相异或得到，且不能得到的结果这个数也不能通过异或得到（即两个集合完全等价）。

那么考虑如何构造这个数。异或线性基有以下性质：

等价性：在原数组和在线性基上进行异或计算的结果完全相同。

最小性：是满足等价性的所有集合中元素个数最少的。这要求线性基中不存在异或和为的子集。

最重要的：线性基中每个数的二进制最高位不同。

那么就很好构造了。先给代码：

void gz(int x){
	for(int i=30;i>=0;i--){
		if((x>>i)&1){
			if(!p[i]){
				p[i]=x;
				return;
			}
			x^=p[i];
		}
	}
}
void work(){
	for(int i=1;i<=n;i++){
		gz(b[i]);
	}
}

因为最高位各不相同，所以我们从大到小检测最高位，如果当前线性基没有最高位为当前数的，就把它放进线性基；否则当前数就异或线性基中最高位和它相同的数。正确性显然可以使用归纳法证明。简单理解就是：线性基中的所有数要么直接来源于原数组，要么通过原数组中的数之间异或得到。

那么可以做这题了：先得到的异或和，如果换，那么变化量显然是： ^ 。那么建立^，即求（这里的表示异或和）。

那么就可以对建线性基了。因为线性基的计算和的计算等价，那么就可以用线性基从高到低尝试消去的每一个二进制位即可，时间复杂度。

至于答案的维护：记录得到线性基的每一个数用到了原数组的哪些数即可，可以用bitset快速计算。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000100],b[1000100],p[100],ue[100],vis[1000100];
bitset<35>bt[35];
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void gz(int x,int pos){
	bitset<35>b,c;
	for(int i=30;i>=0;i--){
		if((x>>i)&1){
			if(!p[i]){
				p[i]=x;
				ue[i]=pos;
				c[i]=true;
				bt[i]=b^c;
				return;
			}
			x^=p[i];
			b^=bt[i];
		}
	}
}
void work(){
	for(int i=0;i<=30;i++){
		p[i]=0;ue[i]=0;
		bt[i].reset();
	}
	int n=read();
	int res=0;
	for(int i=1;i<=n;i++) a[i]=read(),res^=a[i];
	for(int i=1;i<=n;i++) b[i]=read()^a[i];
	if(!res){
		for(int i=1;i<=n;i++){
			printf("%d ",a[i]);
		}
		return;
	}
	for(int i=1;i<=n;i++){
		gz(b[i],i);
	}
	bitset<35>ans;
	for(int i=30;i>=0;i--){
		if((res>>i)&1){
			if(!p[i]){
				puts("-1");
				return;
			}
			res^=p[i];
			ans^=bt[i];
		}
	}
	for(int i=0;i<=30;i++){
		if(ans[i]){
			vis[ue[i]]=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]){
			printf("%d ",b[i]^a[i]);
		}else{
			printf("%d ",a[i]);
		}
		vis[i]=0;
	}
	puts("");
}
int main(){
	int t=read();
	while(t--){
		work();
	}
	return 0;
}