线性基
线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。 线性基的性质
线性基有以下几种性质：
- 数组中的所有元素都能够用线性基中的元素相互异或计算出来
- 线性基中不存在异或值为0的子集
- 满足性质1的前提下，线性基中的元素个数是最少的。
- 线性基中每个元素二进制位数均不相同
线性基的计算
对于当前所求出来的线性基，我们在插入一个新的元素时（即使得其表示范围多一个数 x
），要保证插入的元素与其他元素异或不为零。
根据性质4，我们能够通过位运算对插入的元素进行异或计算：
x=p1⨁p2⨁…⨁pi⨁px
pi 为线性基中的某个基，则：
px=p1⨁p2⨁…⨁pi⨁x
根据性质4，我们求解的线性基中不能包含二进制位数相同的数，因此我们把x按照最高位向最低位异或的方式进行计算，假如当前x的二进制最高位所对应的基存在，则x异或这个基（此时x的值会改变），这样能够保证x的二进制位数至少能够减少1位，然后继续进行计算，计算终点有两种结果：
- x二进制最高位对应的基不存在，则把x插入线性基，运算结束
- 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];
}
}
}
投递不鸣科技等公司10个岗位 >