hdu 3949 XOR(线性基)

传送门

解题思路

　　首先构造出线性基，需要对线性基进行改造，就是让(0)~(63)中的每一位只存在于其对应线性基上，也就是高斯消元的过程。这样的话把线性基有值的位拿出，求第(k)小，就是若(k)二进制中第(i)位存在，就使答案异或上线性基中第(i)小。注意(0)的判断。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
const int N=10005;
typedef unsigned long long LL;

template<class T> void rd(T &x){
	x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}

int T,n,Q,cnt;
LL a[70],rk[70];
bool flag;

inline void init(){
	memset(a,0,sizeof(a));
	cnt=0;flag=false;
}

inline void insert(LL x){
	for(int i=64;i;i--)
		if(x&(1ll<<(i-1))){
			if(!a[i]) {a[i]=x; return ;}
			else x^=a[i];
		}
	if(!x) flag=1;
}

inline void Unique(){
	for(int i=1;i<=64;i++){
		if(!a[i]) continue;
		for(int j=i+1;j<=64;j++)	
			if(a[j]&(1<<(i-1))) a[j]^=a[i];
	}
	for(int i=1;i<=64;i++) if(a[i]) rk[++cnt]=a[i];
}

inline void solve(LL x){
	LL ans=0;if(flag) x--;
	if((x>>cnt)) {puts("-1"); return;}
	for(int i=1;i<=cnt;i++)
		if(x&(1ll<<(i-1))) ans^=rk[i];
	printf("%llu
",ans);
}

int main(){
	LL x;rd(T);
	for(int Case=1;Case<=T;Case++){
		printf("Case #%d:
",Case);
		init(); rd(n);
		for(int i=1;i<=n;i++)
			rd(x),insert(x);
		Unique();
		for(rd(Q);Q;Q--)
			rd(x),solve(x);
	}		
	return 0;
}