线性基

好久都没有更过知识点了

• 引入：（可以跳过）
  首先可以看一下这道题（高斯消元会的情况下）：
  然后就会有一个基的概念（虽然我也不能太理解）。
• 概念：（解决异或问题）
  不过线性基就是给定原数列，构建一个新数列，满足原数列的异或和集合=新数列的异或和集合，而且新数列大小尽量小。
• 性质：
  1.集合里按照\(base[0……log_2n]\)存储，bs[i]如果不为0，它的最高位一定是\(2^i\)。
  2.理解:每个insert(y)结束后y都会变为0（说明其中肯定能异或出y）
  3.集合里没有异或和为0的数，判断有没有0可以用性质2
• code
  1.插入值:

bool Insert(int y) {
	for(int i=60;i>=0;i--) {
		if((y>>i)&1) {
			if(!Bs[i]){Bs[i]=y;return;}    //找到了就return,不要忘了
			else y^=Bs[i];
		}
	}
}

2.与k异或最大

ll Mx(ll k) {
	for(int i=60;i>=0;i--) {
		bool val=(k>>i)&1;
		if(!val) {k^=Bs[i];}
	}
	return k;
}

3.任意异或最大值

int mx=0;
for(int i=up;i>=0;i--) {
	if((mx>>i)&1) continue;
	mx^=Bs[i];
}

ps.最小值就先判断有没有异或和=0的，没有就最低位的大于0的bs[i]。
4.第k大：
转化为D[]类线性基，性质:
1.\(2^i\)（第i位）只会在一个D[]的值中存在
2.两个bs[]异或起来一定会大于其中任意一个的值
操作方法，枚举每个bs[i]的每一位，如第j位为1，就看bs[j]>0吗。最后再（把有值的）离散化一下。
所以会发现第k大，刚好就是它二进制位i为1的的Bs[i]异或和。
证明？感性：k=1时就是\((1)_2\),k=2时显然\((10)_2\)每次你都会+1。
理性：\(f((k+1)_2)>f((k)_2)\)单调性可以证明，因为性质1，只要找到第一个字典序严格大于的二进制位置就可以高低立判了。
ps.还需判断0

void re_build() {
	for(int i=60;i>=0;i--) {
		for(int j=i-1;j>=0;j--) {
			if((Bs[i]>>j)&1) Bs[i]^=Bs[j];
		}
	}
	for(int i=0;i<=60;i++)if(Bs[i])D[cnt++]=Bs[i];
}