线性基

1. 介绍

我们称一个$n$ 维向量组是线性无关的，当且仅当不存下不全为 0 的一组数$c_i$，使得$\sum c_i a_i =0$。

而线性基认为是一个$n$ 维向量集合中极大的线性无关向量子集，可以证明任何向量集合存在线性基，且一个向量集合的任意线性基大小相同。

最坏情况下线性基会有$n$ 个元素，即全部都线性无关。我们可以通过维护一个向量数组$a_i$（$i\in [1,n]$）来表示最终得到的线性基。

依次加入每一个向量$v$，从高到低扫描每一位，如果$v$ 的第$i$ 位非零，那么就检查$a_i$：

• 若$a_i$ 不存在，那么令$a_i \leftarrow v$，结束循环。
• 若$a_i$ 存在，那么令$v \leftarrow \dfrac{v_x}{a_{i,x}}a_i$，继续循环下一位。

上述算法时间复杂度为$O(n^2 m)$，其中$m$ 为加入的向量数量。溶蚀如果一个向量可以通过上面的过程循环到最后一位，最终变为零向量的话，说明这个向量可以被这一组线性基所表示。

在 OI 中，相较于上面我们我们所说的$n$ 维实线性空间$\mathbb{R}^n$ 下的实数线性基，一般的我们研究的更多的是布尔线性空间下的异或线性基。

那么在异或线性基中，一个把一个数的二进制位看做一个向量，即一个向量等价于一个$[0,2^n)$ 内的整数。

其中加法等价于按位异或，数乘等价于且。

那么同等于上面，异或线性基中的数线性无关等价于异或和不为 0。一个数如果能够被线性基表示，那么等价于被表示成数集中若干个数的异或和，也就是数集的子集异或和。

异或线性基的插入其实和实数线性基是差不太多。

我们加入一个数$v$，从高到低扫描每一个二进制位，如果$v$ 的第$i$ 位非零，那么检查$a_i$：

• 若$a_i$ 不存在，那么令$a_i\leftarrow v$，结束。
• 如果$a_i$ 存在，那么令$v\leftarrow v \operatorname{xor} a_i$，继续循环。

时间复杂度为$O(\dfrac{n^2 m}{\omega})$，但是我们位运算的话在位数$n<64$ 的情况下一般认为是$O(nm)$。

代码如下：

void insert(int x){
    for(int i=52;i>=0;i--){
        if((x>>i)&1){
            if(!p[i]){
                p[i]=x;
                break;
            }
            x^=p[i];
        }
    }
}

线性基有一些性质，这里我们举例异或线性基，性质同样适用于实数线性基：

1. 原序列的任意一个数都可以由线性基内部的一些数异或得到。
2. 线性基内部的任意数异或起来都不能得到 0。
3. 线性基内部的数个数唯一；且在保持性质一的前提下，数的个数是最少的。

证明如下：

1. 显然。因为我们是极大线性无关集，那么把线性无关的都放进去，剩下了向量一定能被线性表示出来。
2. 线性无关也就是说互相不能线性表示出来，根据最开头我们提到的线性无关定义是显然的。
3. 若去掉线性基里面的任一个数，都会使得原序列里的数无法通过用线性基里的元素线性表示得到，没有多余的元素。所以线性基的元素个数在保持性质一的前提下，一定是最少的。

2.线性基操作

插入

上面提到了：

void insert(int x){
    for(int i=52;i>=0;i--){
        if((x>>i)&1){
            if(!p[i]){
                p[i]=x;
                break;
            }
            x^=p[i];
        }
    }
}

求最大值

考虑贪心，初始答案为 0，从线性基的最高位开始，若当前答案异或线性基可以让这个答案变得更大，那就异或它。根据性质 1 容易证明这是对的：

int getmx(){
    int ans=0;
    for(int i=52;i>=0;i--){
        if((ans^p[i])>ans) ans^=p[i];
    }
    return ans;
}

求最小值

如果求的是线性基$p$ 能表示出的异或的最小值，那么就是最小的$p_i$，原因是线性无关且异或是不进位加法。

如果是整个序列，要另外检查有没有元素不能插入线性基，如果有，那么最小值就是 0，否则依然是最小的$p_i$。

求第 k 小

从一个序列中取任意元素进行异或，求能异或出的所有数字中第$k$ 小的那个。

收先预处理线性基$p$，对于每一个$p_i$，枚举$j=i\sim 1$，如果$p_i$ 二进制第$j$ 位为 1，那么让$p_i$ 异或上$p_{j-1}$。

将$k$ 转为二进制，假如第$i$ 位为 1，则$ans$ 异或线性集中第$i$ 个元素。

能否被异或

尝试把一个数插入线性基，如果可以插入说明不能，反之可以。

线性基求并

一个线性基元素插入到另一个线性基即可。时间复杂度$O(\log^2 |V|)$，其中$V$ 为值域。

求交不太会呜呜。

3. 前缀线性基

例题：CF1100F

询问相当于求区间$[l,r]$ 内$c_i$ 构成的一组线性基。

当然我们可以通过线段树维护，时间复杂度$O(n \log^2 |V|+q\log n \log^2 |V|)$，很那泵。

我们先想一想，为什么区间查的线性基不能用全局的维护，某种意义上也就是为什么线性基不支持删除。

答案是我们根本不知道线性基每一位数是如何组成的，我们不知道线性基上每一位数的位置，这就导致我们不知道在区间查询的时候能不能选择某一位。

一般构造线性基的方法是增量构造，也就是我们上面所说的一个一个插入。枚举$i=1\sim n$，依次尝试把$a_i$ 插入到线性基中。

那么在加入$a_r$ 之后，当前线性基对应的就是$[1,r]$ 构成的线性基。如果此时能够想办法仅考虑$l\le i$ 的$a_i$，那么也就得到了$[l,r]$ 构成的线性基。

说人话就是我们希望当前的线性基中$a_i$ 的$i$ 尽可能大，加入的时间尽可能晚。

那么在前面构造线性基的方法中，如果我们当前加入的是$v$，会在$a_i$ 存在的时候直接对$v$ 进行修改，但是由于$v$ 加入的时间比$a_i$ 晚，而$v,a_i$ 在当前位置的地位是等价的，所以我们可以将$a_i,v$ 进行交换，让加入时间更晚的$v$ 留下，让原本线性基中的$a_i$ 代替$v$ 去做接下来的处理。

那么我们可以维护线性基的同时，维护线性基内每一个元素对应的原数下表$tim_i$，那么区间查询的时候只考虑那些$tim_i \ge l$ 的元素即可，时间复杂度是$O(\log |V|)$。

这样的结构，我们叫做前缀线性基或者时间戳线性基。

总时间复杂度$O((n+q)\log |V|)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5e5+15,MP=32;
int n,q,a[MN];

struct prexxj{
    int num,pos[MN][MP],p[MN][MP];

    void insert(int x){
        num++;
        for(int i=0;i<MP;i++){
            p[num][i]=p[num-1][i];
            pos[num][i]=pos[num-1][i];
        }
        int P=num;
        for(int i=MP-1;i>=0;i--){
            if((x>>i)&1){
                if(!p[num][i]){
                    p[num][i]=x;
                    pos[num][i]=P;
                    break;
                }else{
                    if(pos[num][i]<P){
                        swap(pos[num][i],P);
                        swap(p[num][i],x);
                    }
                    x^=p[num][i];
                }
            }
        }
    }

    int getmx(int l,int r){
        int ans=0;
        for(int i=31;i>=0;i--){
            if(pos[r][i]<l) continue;
            if((ans^p[r][i])>ans) ans^=p[r][i];
        }
        return ans;
    }

}pxj;

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pxj.insert(x);
    }
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<pxj.getmx(x,y)<<'\n';
    }
    return 0;
}

4. 例题

P4301 新 Nim 游戏

没有第一回合那就是传统的 Nim 游戏，先手有必胜策略当且仅当所有$a_i$ 异或起来不为 0。

那么考虑第一回合后后手的操作，假设第一回合后石子的集合是$S$，那么其可以保留该石子集合的任意子集。而后手只需要是的保留的子集异或和为 0，他就可以获得胜利。

所以第一回合先手要想获胜，必须让$S$ 集合不能存在任何一个非空子集使得里面所有元素异或和为$0$。

由异或线性基的性质，元素异或和不为 0。我们可以通过这个性质入手，但是同时由于先手第一回合要尽可能少地取
石子，那么也就要让$S$ 中的元素和尽可能大。

那么可以得到$S$ 是元素和最大的那一组线性基，我们每一次贪心的将$a_i$ 从大到小贪心的加入线性基，那么最后得到的线性基就是$\sum a_i$ 最大的线性基。

时间复杂度$O(k\log |V|)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e5+15;
int n,a[MN],p[MN],ans;

bool cmp(int x,int y){
    return x>y;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        int x=a[i];
        for(int j=30;j>=0;j--){
            if((x>>j)&1){
                if(!p[j]){
                    p[j]=x;
                    break;
                }else x^=p[j];
            }
        }
        if(!x){
            ans+=a[i];
        }
    }
    cout<<ans;

    return 0;
}

CF895C

完全平方数有一个性质，就是在质因数分解下的表示，所有质因数的指数都是偶数。

而本题目只需要让我们判断是否质因子全为偶数即可，根据奇偶性的表示，就是一个 0/1 表示。

考虑到$|V|\le 70$，也就是说质数一共只有 19 个，考虑每一个数对应一个 19 维的布尔向量，那么问题转化为有多少种线性组合的方式使得异或和为 0.

先建异或线性基，那么不在线性基里面的元素一定能够被线性基内的元素所线性组合切以一一对应，那么线性组合后异或的和为 0.

设线性基内元素数量为$k$，则最终答案不在线性基内元素任选的方案数，为$2^{n-k}-1$（把所有元素都不选的去掉）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=55,MOD=1e9+7;
int n;
int pri[30] = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 } ;

struct xxj{
    int p[MN];

    void insert(int x){
        for(int i=19;i>=0;i--){
            if((x>>i)&1){
                if(!p[i]){
                    p[i]=x;
                    break;
                }
                x^=p[i];
            }
        }
    }
}xj;

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,ret=0;
        cin>>x;
        for(int j=0;j<19;j++){
            if(x%pri[j]==0){
                int now=0;
                while(x%pri[j]==0){
                    x/=pri[j];
                    now^=1;
                }
                ret^=(now<<j);
            }
        }
        xj.insert(ret);
    }
    for(int i=0;i<=19;i++){
        if(xj.p[i]) n--;
    }
    cout<<(ksm(2,n)-1)%MOD;
    
    return 0;
}

P4570 元素

和上面例题一样，按顺序尝试将每个元素插入线性基中，如果能插入就累加答案。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int mp=65,mn=1520;
int n;
pir a[mn];

struct xxj{
    int p[mp],ans=0;

    void insert(int x,int y){
        for(int i=63;i>=0;i--){
            if((x>>i)&1){
                if(!p[i]){
                    p[i]=x;
                    ans+=y;
                    break;
                }
                x^=p[i];
            }
        }
    }
}xj;

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].second>>a[i].first;
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--){
        xj.insert(a[i].second,a[i].first);
    }
    cout<<xj.ans;
    return 0;
}

P4151 WC2011 最大 XOR 和路径

我们先从一条$1\to n$ 的路径，让后向外拓展。显然只有环对答案有影响，因为非环的边一定会走两次，异或和为 0。

因为图是连通的，所以可以经过任意环，把所有的环的异或值扔到线性基里，然后再考虑选择哪一条路径。注意到，若从$1$ 到$n$ 有多条路径，其实这些路径也构成了环，也会被加入到线性基里，这时候随便选一条路径即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e5+15,MP=65;
struct Edge{
    int v,w;
};
int n,m,ans,dis[MN];
bool vis[MN];
vector<Edge> adj[MN];

struct xxj{
    int p[MP];
    
    void insert(int x){
        for(int i=63;i>=0;i--){
            if((x>>i)&1){
                if(!p[i]){
                    p[i]=x;
                    break;
                }
                x^=p[i];
            }
        }
    }

    int getmx(int x){
        int ans=x;
        for(int i=63;i>=0;i--){
            if((ans^p[i])>ans) ans^=p[i];
        }
        return ans;
    }

}xj;

void dfs(int u,int fa){
    vis[u]=1;
    for(auto e:adj[u]){
        if(vis[e.v]) xj.insert(dis[e.v]^e.w^dis[u]);
        else dis[e.v]=dis[u]^e.w,dfs(e.v,u);
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dfs(1,0);
    cout<<xj.getmx(dis[n]);
    return 0;
}