线性基求交

参考资料：牛客题解

即对于两个线性空间(V_1,V_2)，求它们的交(V_1cap V_2)

首先，两个线性空间的交显然还是线性空间

引理：若 (V_1,V_2) 是线性空间，(B_1,B_2) 分别是他们的一组基，令 (W=B_2 cap V_1) ，若 (B_1 cup (B2 setminus W)) 线性无关，则 (W) 是 (V_1 cap V_2) 的一组基。

证明：考虑任意(vin V_1cap V_2)，那么(v)可以同时被(B_1)和(B_2)表示出。考虑如何证明(v)可以被(W)线性表示。我们假设不能，那么(v)一定可以被(S)和(T)共同线性表示，其中(Sin W,Tin B_2setminus W)，且其中(T)不为空。那么此时(T)一定与(B_1)线性相关，与我们的假设不符。所以上述假设成立

但是 (B_1 cup (B_2 setminus W)) 有可能线性相关，这时我们只需要换一组基即可。

假如当前加入的元素为 (x) ，若 (x) 不能被 (B_1 cup B'_2) 表示，那么直接在 (B_2') 中加入 (x) 即可；否则 (x) 一定能被 (B_1 cup (B_2' setminus W)) 的恰好一个子集表示，设 (x= ext{xor(S) ^ xor(T)}) ，其中 (S subseteq B_1,T subseteq B_2' setminus W) ，在 (B_2') 中加入 ( ext{xor(S)}) 即可，且此时(Sin W)，在(W)中也加入(S)即可

总复杂度(O(d^2))，其中(d)为维数

#define int unsigned int
Base merge(Base a,Base b){
	Base na(a),tmp(a),gl;
	int cur,d;
	fp(i,0,31)if(b[i]){
		cur=0,d=b[i];
		fd(j,i,0)if(d>>j&1){
			if(tmp[j]){
				d^=tmp[j],cur^=na[j];
				if(d)continue;
				gl[i]=cur;
			}else tmp[j]=d,na[j]=cur;
			break;
		}
	}
	return gl;
}