基（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

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

题解：

先找出一个 dfs 树，考虑在什么情况下无向图会变得不连通。

当且仅当存在一条树边，满足所有覆盖这条树边的返祖边和这条树边都被删除时，无向图不连通。

那么如何判断是不是存在这样一条树边呢，我们可以给每条返祖边随机一个权值，每条树边的权值就是所有覆盖它的返祖边的权值异或和。对于一次查询，如果查询的边权线性相关说明一定能找到一个子集异或和为 0，也就是满足无向图不连通的条件了。

参考文献

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