线性基

线性基-OIWIKI

算法｜线性基学习笔记

struct basis{
	ll a[64];
	void reset(){memset(a,0,sizeof(a));}
	void insert(ll x){
		for(int i=63;i>=0;i--){
			if(x&(1ll<<i)){
				if(!a[i]){
					a[i]=x;break;
				}
				x^=a[i];
			}
		}
	}
	bool exist(ll x){
		for(int i=63;i>=0;i--){
			if(x&(1ll<<i)){
				if(a[i])x^=a[i];
				else {return 0;}
			}
		}
		return 1;
	}
}t;