线性基

线性基

这东西本质上就是高斯消元

qaq

问题

我们有一个长度为n的序列，问序列中任选若干个能得到的异或最大值

我们考虑把每个数变为二进制，然后将其放入矩阵中

例如

3,4,5,10,15

0 0 1 1

0 1 0 0

0 1 0 1

1 0 1 0

1 1 1 1

然后对其异或高斯消元

也就是变成一组线性无关的基底

并且主元所在列只有主元这一个1[高斯消元一边就会变成这个样子]

然后你想求异或最大值就从最上面往下拿就行了

如果这一位还不是1，就异或上答案

否则就不拿

由于高斯消元复杂度不优

我们考虑更优秀的做法

//p[i]表示第i位为主元（1）的线性基
void ins(int x){
	for(int i=62;i>=0;i--){
		if((x&(1ll<<i))==0)continue;
		if(!p[i]){//若这一位的线性基不存在，直接等于它
			p[i]=x;
			return ;
		}
		x^=p[i];//把这一位清0，看往下走能否有用
	}
}

这样也能构造一组基

但想达到高斯消元的效果(p[i]有值，所有j>i的线性基,第i位都不为1)

我们需要下面的再操作

for(int i=62;i>=0;i--)
	for(int j=i-1;j>=0;j--)
		if(p[i]&(1<<j))
			p[i]^=p[j];

而得到了这样的有什么用呢qaq

考虑我们想知道序列异或的第k小值

我们考虑把k二进制分解

由于我们刚刚得到的线性基的优秀性质

只有p[i]这个线性基第i位为1

那么对于k的二进制分解

可以证明我们对于每个i且k的第i位为1

我们异或上从大到小的第i-1个有值线性基就好了

板子

#include<bits/stdc++.h>
#define int long long
using namespace std;
int tot=0;
int p[64],pos[64];
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void ins(int x){
	for(int i=62;i>=0;i--){
		if((x&(1ll<<i))==0)continue;
		if(!p[i]){
			p[i]=x;
			return ;
		}
		x^=p[i];
	}
}
void pre(){
	for(int i=62;i>=0;i--)
		for(int j=i-1;j>=0;j--)
			if(p[i]&(1<<j))
				p[i]^=p[j];
	for(int i=62;i>=0;i--)
		if(p[i])pos[tot++]=p[i];
	tot--;
	return ;
}
int query(int x){
	if(!x)return 0;
	int ans=0;
	for(int i=62;i>=0;i--)
		if(x&(1ll<<i)){
			if(tot<i)return -1;
			ans^=pos[tot-i];
		}
	return ans;
}
signed main(){
	int t,cas=0;
	t=read();
	while(t--){
		int n,q;
		n=read();
		tot=0;
		memset(p,0,sizeof(p));
		memset(pos,0,sizeof(pos));
		for(int i=1;i<=n;i++)ins(read());
		pre();
		q=read();
		int val=(n>tot+1);
		printf("Case #%d:\n",++cas);
		for(int i=1;i<=q;i++){
			int k;
			k=read();
			printf("%lld\n",query(k-val));
		}
	}
	return 0;
}