线性基是向量空间的一组基，通常可以解决有关异或的一些题目。 ——OI Wiki
线性基就是从初始集合中选出的一个子集，它满足一些性质，可以处理一些问题（屁话）。
性质
- 线性基中每个元素二进制下最高位是不同的。
- 线性基中没有异或和为 \(0\) 的子集。
- 线性基中任意子集中元素异或和的值域等于原集合的值域，且集合大小最小。
构造
考虑这样一个问题：
求一个集合任意元素异或和的最大值。
首先我们回想一下异或的性质：如果二进制某一位相同的两个数，那么这一位就为 \(1\)，反之为 \(0\)。特别地，异或这一运算满足交换律。
思考什么时候异或和最大？我们希望的肯定是最终值二进制下 \(1\) 的个数越多越好，换言之，最高位的 \(1\) 越靠前越好。
因为异或是按位操作，所以当靠前的一位确定下来后，后面的几位不管怎么搞都不会对前面的这一位产生影响。
所以得到一个类似贪心（？）的算法：
假设我们要往线性基中插入一个数 \(x\)，其最高位为 \(d\)。
- 若 \(d\) 位未被插入过值，则往 \(d\) 位插入 \(x\)。
- 反之，将 \(x\) 异或上当前第 \(d\) 位上的 \(y\)，往下一位进行扫描，直到变成 \(0\) 或者被插入。
为什么 \(x\) 要异或上 \(y\) 呢？
因为任何一个数二进制的最高位都是 \(1\)。在同一个位置遇到了已经插入过的数证明两个数最高位相同，此时异或一下，使要插入的值最高位变成 \(0\)，再去判断新的最高位找一个新的位置插入。是为了尽可能使二进制的每一位都可以有 \(1\)，且可以证明对答案无影响。
代码：
void insert(int x){
for (int i = len;i >= 0;i--){ // len 为二进制数最大长度，因题目而异
if (!(x & (1ll << i))) continue; // 判断 x 的当前位是否为 1
if (!p[i]) { p[i] = x; return ; } // 插入成功
x ^= p[i]; // 插入失败就异或，枚举下一位
}
}
参考资料
- KnightL 的 cnblogs 文章：线性基