基(basis)是线性代数中的一个概念,它是描述、刻画向量空间的基本工具。而在现行的 OI 题目中,通常在利用基在异或空间中的一些特殊性质来解决题目,而这一类题目所涉及的知识点被称作「线性基」。

有关向量空间(Vector Space)、线性无关(linearly independent)、线性组合(linear combination)、张成(Span)、基(Basis)的概念就不讲了,请自行了解。

线性基

简单来说,线性基维护的是异或空间下的若干个线性无关向量,它们组成一个矩阵。在实现时我们使用表示最高位为第位且为的向量的值。

线性基可以使用上三角矩阵维护,插入一个向量时需要消元,复杂度。在特殊题目的要求下可能需要消元成对角矩阵,这时的插入复杂度就是

线性基的合并就是暴力插入的过程,复杂度

HDU3949 Xor

求去重后异或第小。

消成对角矩阵的线性基可以解决异或第 K 小的问题。由于是模板题所以给出核心代码:

/******************heading******************/

int n;

long long b[70],lb;
long long p[70],lp;
bool insert(long long x){
    ROF(i,63,0){
        if(!(x>>i&1))continue;
        if(!b[i]){
            b[i]=x,lb++;
            ROF(j,i-1,0) if(b[i]>>j&1)b[i]^=b[j];
            FOR(j,i+1,63) if(b[j]>>i&1)b[j]^=b[i];
            return 1;
        }
        x^=b[i];
    }
    return 0;
}
void print(){
    int len=0;
    FOR(i,0,63)if(b[i])len=i;
    FOR(i,0,len){
        ROF(j,len,0) printf("%lld",b[i]>>j&1);
        puts("");
    }
}
void work(){
    FOR(i,0,63) if(b[i])p[lp++]=b[i];
}
void clear(){
    memset(b,0,sizeof(b));
    lb=0,lp=0;
}
long long query(long long x){
    long long res=0;
    FOR(i,0,63)if(x>>i&1)res^=p[i];
    return res;
}
void go(){
    cin>>n;
    clear();
    bool fl=0;
    FOR(i,1,n){
        long long x;
        cin>>x;
        if(!insert(x))fl=1;
    }
    work();
    long long lim=(1ll<<lb)-1;
    int q;
    scanf("%d",&q);
    FOR(i,1,q){
        long long x;
        cin>>x;
        if(fl)x--;
        if(x>lim)cout<<-1<<endl;
        else cout<<query(x)<<endl;
    }
}
int main(){
    int t;
    cin>>t;
    FOR(i,1,t)cout<< "Case #" << i<< ":" <<endl,go();
    return 0;
}

平方数的套路

有时要求一段区间选若干个数乘积的平方数。记录每一个数的质因数次数的奇偶性,即一个 01 向量,就转化为异或和为 0 的问题。如果他们线性相关就有解,否则无解。

带删除的线性基

形式化地,我们要求支持:

  • 插入一个数
  • 删除一个数
  • 求这个集合的线性基

算法一

我们可以求出每个数的存在时间。然后在时间线段树上 DFS 即可。复杂度是的。

BZOJ4184 shallot

例题:最大 xor 路径。

算法二

我们也有更优秀的做法。

插入,我们直接按照线性基的方式插入即可。

但删除就有一些问题。

如果不在线性基里:直接删了完事。

如果在线性基里,那么我们就需要做两件事:

  1. 消除在线性基中的影响。
  2. 可能在删除后,有新的数可以被加到线性基中。

第一部分

我们知道,把插入到线性基中时,会先异或一些基,最后当找到一个没有被 span 的维度(基)那么就做为一个新的基加入到线性基中(就是异或到最后的那个数)。

而在之后插入的数中,有一部分基会异或,那么这些基里就含有的影响。我们要做的就是消除这些影响。

方法 1:我们可以直接拿异或这些基然后再删除(异或自己),这样的确能消除影响,但问题是你这么搞完之后,线性基就不一定是上三角矩阵了,你还得想办法维护一下。

方法 2:方法 1 的问题的出现原因是异或过的基都比小。因此我们不妨找到异或过的基中最小的基,记做。那么里有什么?它有的影响,和除了之外的影响(废话)。我们的目的是消除所有的影响——也就是给他异或一个上去。我们不妨用异或所有的,异或过的基。

  • 异或上,它相当于把消除的影响后放到的位置上。
  • 异或其他基时尽管会顺带将的部分影响加到(去掉)这个基上,但这无关紧要。因为的基它还在(在的位置上)
  • 异或自己时,它把自己删掉了。但这无所谓,因为的位置就是它新的位置。

这么一番操作,没了还在。我称之为借刀自杀。

第二部分

接下来的问题是,你删了对应的后,可能会有线性基外面的数能够加到线性基中。那么哪些数能被加进来?在之前的线性基表示中包含了的数。于是我们记一个表示在线性基外面包含的数的集合。那么我们在里面随便选一个数,然后在它的线性基表示的集合中删掉,把插入后令即可。

算法三

上述算法中会用到 set,在较大的数据范围(2e6)下运行速度较慢。我们有常数更小的离线做法。

在删除的时候我们要消除在线性基里的影响。那么如果本身就是最后一个被加入的数呢?那我们直接删了它就完事了。

离线的时候,我们可以计算出每个数的删除时间。进而可以在线性基里维护每个基的删除时间。当插入一个数的时候,如果它当前异或的基的删除时间比它早,那么我们不如直接交换这个基和你当前的数。让你当前的数代替这个位置,让那个基来继续执行插入的操作。容易发现这样构造的线性基,小的基的删除时间都比大的基早,因此删除就可以直接删除了。

时间复杂度仍是,如果使用排序而不是 set,常数会比较小。

线性基的一个神奇应用

BZOJ3569

通过随机赋权,判断是否线性相关的方式来判图是否连通。

参考文献

https://blog.csdn.net/a_forever_dream/article/details/83654397