线性基概念

在这里插入图片描述
B成为线性基
这个过程其实相当于将S压缩成B

构造线性基

在这里插入图片描述
在这里插入图片描述
线性基满足特殊性质：

若a[i]!=0（即主元i存在），则线性基中只有a[i]的第i位是1；且此时a[i]的最高位就是第i位

为了实现这个性质需要用特殊的insert方法：
（为了确保有主元的一列只有一个1）
如果第j位是主元不是自由元，那么要始终保持第j列只有第j行中的一个1:
对于插入的x，最高位1是第j位，查看第j-1位到第0位是否已经有1存在，如果存在就将x的该位异或。还要将其他行的第j位异或掉
详细过程见下图
在这里插入图片描述

代码：

bool insert(ll x){
    for(int j=L;j>=0;--j){//从最高位开始看
        if((x&(1ll<<j))==0) continue;

        if(a[j]){//若如主元j已经存在，用a[j]消去x的第j位然后继续
            x ^= a[j];
            continue;
        }   

        //让x当主元j，需要先用第k(k<j)个主元消去x的第k位
        for(int k=j-1;k>=0;k--){
            if(x & (1ll<<k)) x ^= a[k];
        }
        //接着用x去消掉第k(k>j)个主元的第j位
        for(int k=L;k>j;k--){
            if(a[k] & (1ll<<j)) a[k] ^= x;
        }
        a[j] = x;
        return 1; 
    }
    return 0;
}

满足特殊性质的线性基可以方便地支持一下几个操作：

  1. 求任意子集xor最大值: 把线性基中所有元素xor起来
  2. 求任意子集xor最小值: 等于最小的主元
  3. 查询x是否在值域中: 如果x能插入线性基，则x不能被当前线性基xor出来
  4. 查询第k小的值: 把k进行二进制分解，把1对应位置的主元xor起来；注意这里第0 小就是0
  5. 求任意子集与x进行xor的最大值：从高->低贪心，若xor上a[j]能变大就xor