「专题」线性基

线性基性质

1. 线性基中所有的数都可以经过一些异或操作还原出原数列。
2. 线性基任意几个元素异或起来不为 \(0\)。
3. 若这是原数列的线性基，那么这一定是满足性质 1,2 的元素最少的一种构造方案。

线性基推论

1. 最多需要 \(\mathrm {log_2(a)}\) 个数，就可以通过异或操作转化为一个数列。

构造线性基

void add(LL x, int val) {
	for(int i = 62; i >= 0; i --) {
		if((x >> i) & 1) {
			if(!p[i]) { p[i] = x; break; }
			else x ^= p[i];
		}
	}
}

证明性质 1：

1. 如果 x 被异或到了 \(0\)，那么一定存在一些线性基里的数可以异或得到它。
2. 如果执行 p[i]=x，显然也可以。

证明性质 2：
异或为 \(0\) 的话，本应该加进去的时候经过一些异或就变成 \(0\) 了，矛盾。

证明性质 3：yy 一下就可以了吧。可以证明加入的顺序不改变线性基的元素个数。

另外，这个也可以判断一个数是否能被一些数异或得到。

求最大值
例题

for(int i = 60; i >= 0; i --) if((ans ^ p[i]) > ans) ans ^= p[i];

位运算的经典贪心，不展开了。

求最小值

1. 线性基内元素个数 < 原数列元素个数，那么加的时候一定有一个数异或成了 \(0\)，所以全局最小值是 \(0\)。
2. 线性基内元素个数 = 原数列元素个数，贪心，选 \(p[0]\)。

求k小值
例题
先咕着。

合并
哈哈这个标题是诈骗的。
实际上枚举暴力差既可以了，时间复杂度：\(O(\log_2^2(n))\)。

元素删除
哈哈也咕了。
例题
[BJWC2011]元素
[TJOI2008]彩灯
CF1100F Ivan and Burgers
SCOI 2016 幸运数字

参考博文