线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。

线性基的性质

线性基有以下几种性质:

  1. 数组中的所有元素都能够用线性基中的元素相互异或计算出来
  2. 线性基中不存在异或值为0的子集
  3. 满足性质1的前提下,线性基中的元素个数是最少的。
  4. 线性基中每个元素二进制位数均不相同

线性基的计算

对于当前所求出来的线性基,我们在插入一个新的元素时(即使得其表示范围多一个数 x

),要保证插入的元素与其他元素异或不为零。

根据性质4,我们能够通过位运算对插入的元素进行异或计算:

x=p1p2pipx

pi 为线性基中的某个基,则:
px=p1p2pix


根据性质4,我们求解的线性基中不能包含二进制位数相同的数,因此我们把x按照最高位向最低位异或的方式进行计算,假如当前x的二进制最高位所对应的基存在,则x异或这个基(此时x的值会改变),这样能够保证x的二进制位数至少能够减少1位,然后继续进行计算,计算终点有两种结果:

  1. x二进制最高位对应的基不存在,则把x插入线性基,运算结束
  2. x值变为0,说明当前线性基能够表示最开始的x,则直接结束。

这样就能够求出来 px

的值,即线性基需要插入的元素。

代码如下:
void update(int x){
    for(int i=30;i>=0;i--){
        if(x>>i){
            if(!f[i]){
                f[i]=x;
                return ;
            }
            x^=f[i];
        }
    }
}