线性基

今天学习了线性基

线性基就是用了一个贪心的手法，使得维护这一位一直是1。
线性基中不含重复的异或。
它的构造方法是，每次取某个数字的最高位值。如果存在过直接异或，否则令线性基等于这个值。

线性基的构造代码还是挺简洁的

void init (lol box) {
	for(int i=50;i>=0;i--) {
		if(!(box>>i&1)) continue; 
		if(!arr[i]) {++cnt,arr[i]=box;break;}
		else box^=arr[i]; 
	} 
}

通过线性基可以求得最大/最小异或和 、 第k最小异或和 、 构造不同方案数量。

构造的不同方案的数量 = 1<< 构造的数量

另外线性基有以下几个性质：