简介

因为我太蒟了，所以这里谈论的线性基都是异或线性基

线性基，可以用来维护有关异或的一些操作

常见的有求最大异或值，某个数能否被一些数异或出来等

线性基都可以用较优的时间复杂度求出

构造

构造线性基的本质是利用高斯消元

对于每个数，从高到底枚举二进制下每位

然后找到最高位为1的那位，和线性基维护的那一位比较

如果线性基的为0，就把数插入到线性基

否则和线性基维护的那一位异或，消去最高位的1，继续往下查找

这样就实现了插入

看代码最好理解了

il void ins(ll x)
{
    for(int i=63;i>=0;i--)
    {
        if(!(x>>i)) continue;//此位为0，继续往后找为1的最高位
        if(!b[i])//如果线性基为0就插入
        {
            b[i]=x;
            break;
        }
        x^=b[i];//否则异或继续往下查找
    }
}

存在性判断

由高位到地位判断是否有1，有1就异或掉最高位，如果最后为0则一定可以表示出这个数，否则一定不能

代码

il bool qry(ll x)
{
    for(int i=63;i>=0;i--)
    {
        if(x&(1ll<<i)) x^=b[i];
    }
    return !x;
}

最大异或和查询

还是从高到低，如果与当前答案异或后更大就异或，反之不异或

代码

il ll qrymax()
{
    ll res=0;
    for(int i=63;i>=0;i--)
        if((res^b[i])>res) res^=b[i];
    return res;
}