【线性基小记】

定义

对一个数的集合\(S\)，其线性基就是由最少的数构成的集合\(B\)，满足在\(S\)中任选一些数异或后的值，都可以在\(B\)中选一些数异或使得两个值相等。

性质

1. \(B\)中任意元素异或起来结果不为\(0\)
   ps：即要求\(B\)中元素线性无关，否则一定可以删掉至少一个数，使得\(B\)能表示的数集不变。
2. 为了方便，我们钦定\(B\)集合中任意两个数的最高位不同（若存在相同，则可以用其中一个异或上另一个，然后往跟低位去插入）

插入

利用性质2，我们设\(b_i\)为\(B\)中最高位为第\(i\)位的数，若没有，则为\(0\)。

初始\(S\)为空，\(B\)也为空，假设当前\(S\)新加入一个数\(x\)，考虑\(B\)集合的变化:

从最高位开始，若\(x\)这一位上为\(0\)，则不进行任何操作。否则，如果\(b_i\)有值,就令\(x\)异或上\(b_i\)；如果\(b_i=0\),就令\(b_i=x\)
复杂度\(O(\log V)\)

bool insert(int x)
{
	for(int i=60;~i;--i)
	{
		if(x>>i&1) {
			if(b[i]) x^=b[i];
			else {
				b[i]=x;return 1;//成功插入
			}
		}
	}
	return 0;//插入失败
}

推论

设\(S\)的值域上界为\(2^n-1\),则\(B\)最多有\(n\)个数

证明：考虑插入的时候记录的\(b_i\)，当每一位上\(b_i\)都有值时，任意一个元素都不可能再插入到线性基中，也就是说\(n\)就是线性基大小的上限。

合并线性基

合并两个线性基\(S_1,S_2\)，只需把一个集合中的元素全部插入另一个集合中，复杂度\(O(\log^2 V)\)

经典模型

1. 求一个集合中能够异或出的最大值
   从高位开始贪心，如果异或上\(b_i\)，能使得结果更大，则异或。

int get()
{
	int x=0;
	for(int i=50;~i;--i)
	{
		if((x^b[i])>x) x^=b[i];
	}
	return x;
}

2. 求一个集合中能够异或出的第k小值