初中生都能看懂的线性基详解
flywen
·
·
算法·理论
Part.0 前言
你是否曾经对数学感到无比恐惧？那太好了，我现在也是。
学习线性基，成为基佬。
线性基，一个近年加入考纲的内容，光看名字就劝退一群像我这样的蒟蒻。但也别被我误导，回头看看，好像也不是很难嘛（逃）。
分享一下我学习线性基的经历：2025 年暑假听金牌老师在上面列各种诡异符号式子。最近想重学线性基，却发现 oi.wiki 上的内容高深复杂，网上题解博客比较杂碎，讲得太简略，不适合我这种蒟蒻理解，毕竟每个人对线性基的接受能力都不一样。
这篇文章个人认为通俗易懂，非常适合像我这样没有线性代数基础的选手。本文含有大量个人理解，如有偏差请指出，希望对大家有帮助。
$\mathrm{2026.7.22}$：修复一些代码上的疏漏（第 $k$ 大异或和与线性基求并）；修改排版；新增题目 [P14994 异或最短路和](https://www.luogu.com.cn/problem/P14994)，[P15044 [UOI 2022 II Stage] 树](https://www.luogu.com.cn/problem/P15044)，[P17127 [ICPC 2025 Shanghai R] Gemcrate](https://www.luogu.com.cn/problem/P17127)。
$\mathrm{2026.7.26}$：感谢 @[ZHR100102](https://www.luogu.com.cn/user/947153) 对于线性基求交的勘误。
麻烦善良的管理员请通过一下。
---
### 记号约定
关于线性代数的部分往往表述可能有偏差，但尽量保证读者能够简单理解。
鉴于信息学中常用布尔向量空间下的线性基，**线性基一般都指异或线性基**。
通常不区分时间复杂度渐进上界和渐进紧确界。时间复杂度中为显示代码流程有时不省略低阶项。
$V$ 一般指值域。$a_i$ 的含义请注意区分，可能是题目中的序列，也有可能是线性基的基底。
---
### 代码
本人代码风格一坨，就看个乐吧。尽量保持和正文一样的变量名。代码部分模板不会再放。
---
### 相关链接
* [题单链接](https://www.luogu.com.cn/training/1036152)
# Part.1 前置知识
*线性基，一听就是很高级的玩意，所以我们必须先了解一些定义。如果您已系统学习过线性代数，可以跳过本版块。*
---
首先，你至少要会二进制运算和集合吧。集合，默认是指不可重的，代码中可以视为为 `set`。
---
### 向量
**向量**（Vector），数学意义为 $d$ 维空间中的有向线段。
我们可以理解为 $d$ 维下的一个坐标。一般来说，向量一般这样表示：
$$\mathbf{x}=(x_1,x_2,\cdots,x_d)$$
向量的线性运算有：
* 与向量的加法，就是直接按维度相加。
* 实数的乘法——数乘，就是每个维度都乘上该实数。
向量线性运算的结果均为向量。
信息学中，可以视为长度为 $d$ 的一维数组。我们常用到**布尔向量**，即每一维数值都对 $2$ 取模，为 $0$ 或 $1$。如果维度较少，int 和 long long 就能够存储布尔向量，否则可以使用 bitset。对于布尔向量，加法为**按位异或**操作，数乘为**按位与**操作。
---
### 线性组合
现在考虑你有无数张某些面值的纸币，你能支付给我的金额有哪些？从你的角度考虑，金额不包括负数。
我们可以将纸币当做 $1$ 维的向量，那么任意张纸币能凑出的金额称作它们的**线性组合**。
**线性组合**（Linear Combination），表示一个向量集合 $S=\{v_1,v_2,\cdots,v_n\}$ 中的向量经过线性运算得到的结果向量。
设 $a_1,a_2,\cdots,a_n$ 为任意一组实数系数（**在纸币的场景中系数是自然数**），则 $S$ 能够线性组合出：
$$v_0=\sum\limits_{i=1}^na_iv_i$$
也称向量 $v_0$ 能被 $S$ 线性表示。
对于布尔向量，$a_i$ 通常只为 $0$ 或 $1$，因为别的系数都没有意义或者运算结果与 $a_i=0$ 或 $1$ 相同。
---
### 线性空间
这些纸币能凑出的所有金额称作这些向量张成的**线性空间**，而该线性空间显然还是 $1$ 维的（多少金额）。
**线性空间**（Vector Space），表示一个向量集合 $S=\{v_1,v_2,\cdots,v_n\}$ 中的向量经过线性运算得到的所有结果向量构成的空间 $V=\operatorname{span}(S)$。
容易得知线性空间 $V$ 中所有向量的线性组合结果仍然包含于 $V$ 中。换句话说，线性空间 $V$ 对于线性运算是“**封闭**”的。
---
### 线性相关与线性无关
如果我们现在无数张有 $5$ 元和 $10$ 元的纸币，那么我们可以凑出所有 $5$ 的倍数金额。考虑没有 $10$ 元的纸币，我们仍然能凑出 $5$ 的倍数金额，并且没有凑出除 $5$ 倍数以外的金额。那么这个 $10$ 元面值的纸币对我们其实没有任何影响。
我们称 $5$ 元和 $10$ 元面值的纸币**线性相关**的。
对于线性空间 $V$ 的一组向量，如果存在一组不全为 $0$ 的系数使得其线性组合为 $0$，则称这组向量线性相关。注意，这等价于至少**有一个向量可由其余向量线性表示**。
反之，$5$ 元和 $3$ 元面值的纸币去掉任何一种都不能凑出原来所有的金额，我们称它们是**线性无关**的。
若只有系数全为 $0$，才能得到零向量，则称这组向量线性无关。
---
### 基
上一部分已经说明线性相关的向量去掉一部分，对最终张成的线性空间没有影响。本着能省则省的信息学思想，肯定能找到一组数量最少的向量，使得张成的线性空间相同。
**基**（Basis），就是这“**极小且完备**”的向量组，是线性无关的，其向量个数称作**秩**（Rank）。线性空间 $V$ 的基能够线性组合出原线性空间 $V$，并且不存在秩小于基的向量组能够线性组合出 $V$。
容易发现基不是唯一的。
例如面值 $\{3,5,10\}$ 能够张成一个线性空间 $V$，其基为面值 $\{3,5\}$，秩为 $2$。
# Part.2 线性基
*铺垫那么多，终于可以开始讲线性基了。*
---
**线性基**（Linear Basis），顾名思义，一般指异或意义下线性空间的基，也有少数题目需要用到实数线性基。线性基非常适合用于处理与异或相关的极值、第 $k$ 大、存在性等问题。
欸等等，线性基构造还没讲呢。
---
### 线性基构造
线性基的构造方法主要有两种，第一种为贪心，第二种为离线后高斯消元。这里只介绍贪心，至于高斯消元法，个人认为布尔空间意义下，它没有必要专门介绍，如果有兴趣可自行了解。
首先线性基的主要维护信息是基（废话），而秩一定小于等于 $d=\log V$，其中 $V$ 为值域，$d$ 为维度，即给定二进制数的长度，其正确性在看完插入方式后可知。
对于每一个二进制位（维度）$i=0,1\cdots,d$，维护一个向量 $a_i$（初始时不存在）；如果存在，则保证 $a_i$ 的二进制第 $i$ 位为 $1$ 并且高位都为 $0$。
定义函数 $\operatorname{insert}(x)$ 表示插入一个布尔向量 $x$：从高到低枚举二进制位 $i=d,d-1,\cdots,0$，如果 $x$ 的第 $i$ 位为 $1$ 则：
* 如果不存在 $a_i$，将 $x$ 插入到 $a_i$，即 $a_i\leftarrow x$，函数返回“插入成功”。
* 如果存在 $a_i$，则 $\operatorname{insert}(x)$ 相当于 $\operatorname{insert}(a_i\oplus x)$，由于算法的流程，$x$ 的最高位就是 $i$，故直接将 $x\leftarrow x\oplus a_i$。
如果 $i=0$ 时，$x$ 仍然没有插入成功，说明原来的基已经能够表示出 $x$，返回“插入失败”。
可以发现算法保证每次插入完基都是符合要求的，既然如此，秩就不会超过 $d$。不过我们还要证明一下线性基的向量数是极小的，每个向量的贡献就是让第 $i$ 位可以自由选择 $0$ 或 $1$。由于基是线性无关的，故线性基中任意个数的异或和都不同。假设有 $cnt$ 个向量，共能组出 $2^{cnt}$ 个向量，而删去任何一个都会使得线性空间的大小变小。
分析一下时间复杂度：当给定布尔向量维度 $d$ 在 long long 的位宽 $w=64$ 内时，单次插入时间复杂度为 $O(d)=O(\log V)$，**后面的时间复杂度分析均假设** $d\leq w$。当 $d$ 较大时，需要使用 bitset，时间复杂度为 $O(\frac{d^2}{w})$。
注意 `1<<i` 一定要写成 `1ll<<i`，本人连着写漏两次。
```cpp
#define ll long long
#define logV 61
ll a[logV];
void insert(ll x){
for(int i=logV-1;i>=0;--i){
if(!(x&(1ll<<i)))continue;
if(a[i])x^=a[i];
else{a[i]=x;return;}
}
}
```
---
### 异或和存在性
在插入部分我们已经讲到：“插入失败”，说明原来的基已经能够表示出 $x$。故改一下插入的代码就行。
时间复杂度 $O(\log V)$。
```cpp
bool check(ll x){
for(int i=logV-1;i>=0;--i){
if(!(x&(1ll<<i)))continue;
if(a[i])x=x^a[i];
else return 0;
}
return 1;
}
```
---
### 最大异或和 / [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812)
给定 $n$ 个数 $x_i$，选出任意个，最大化异或和。
$n\leq50,0\leq x_i\leq2^{50}$。
---
根据我们的构造，我们可以维护结果 $r$，从高到低位扫过每个二进制位 $i$，如果 $r$ 的这一位为 $0$ 并且线性基的第 $i$ 位存在，为 $a_i$，就让 $r\leftarrow r\oplus a_i$。
这样是正确的，因为异或上 $a_i$ 是唯一的让第 $i$ 位变为 $1$ 的方式，而二进制高位决定大小。
也可以直接写成 $r\leftarrow\max\{r,r\oplus a_i\}$，这是等价的。
时间复杂度 $O(\log V)$，总复杂度 $O(n\log V)$。
```cpp
ll maximum(){
ll r=0;
for(int i=logV-1;i>=0;--i)r=max(r,r^a[i]);
return r;
}
```
---
### 最小异或和
我们需要特判一下 $0$。如果线性空间中没有 $0$，那答案就是 $\min\limits_{i=1}^{\log V} a_i$。
在插入部分我们已经讲到：“插入失败”，说明原来的基已经能够表示出 $x$。故原来表示一个 $x$ 与 $x$ 异或之后就能得到 $0$。
时间复杂度 $O(\log V)$。
```cpp
bool flag0;
void insert(ll x){
for(int i=logV-1;i>=0;--i){
if(!(x&(1ll<<i)))continue;
if(a[i])x=x^a[i];
else{a[i]=x;return;}
}
flag0=1; //元素x插不进去,说明有其他的数能够异或出x,故异或和能等于0
}
ll minimum(){
if(flag0)return 0;
for(int i=0;i<logV;++i)if(a[i])return a[i];
return -1;
}
```
---
### 最大 / 最小线性表示
给定 $x$，求其异或上一些数后的最大 / 最小值。
---
以最大值为例，从高到低位遍历，假设现在是第 $i$ 位，如果 $x$ 的第 $i$ 位为 $1$ 并且存在 $a_i$，就让 $x$ 异或上 $a_i$，原理同最大异或和。
时间复杂度 $O(\log V)$。
```cpp
ll maxrep(ll x){
for(int i=logV-1;i>=0;--i)if(!(x&(1ll<<i)))x^=a[i];
return x;
}
ll minrep(ll x){
for(int i=logV-1;i>=0;--i)if(x&(1ll<<i))x^=a[i];
return x;
}
```
---
### [P3857 [TJOI2008] 彩灯](https://www.luogu.com.cn/problem/P3857)
有 $n$ 个灯，初始都是关的。有 $m$ 个开关，给出分别可以控制的灯编号，求可以变换出来的样式数目，对 $2008$ 取模。
$n+m\leq50$。
---
每个开关可以视作一个布尔向量。前面已经讲过，设线性基的秩为 $cnt$，即有 $cnt$ 个元素，则线性基对应的线性空间有 $2^{cnt}$ 个不同的数。
---
### 第 $k$ 小异或和
注意是所有线性组合去重后，即线性基元素组出的第 $k$ 小。
对于线性基来说，其元素互相异或不改变其表示的线性空间。对于存在 $a_i$ 的二进制位，我们不妨将其消成第 $i$ 位只有 $a_i$ 为 $1$，如此这些位都是独立的。
时间复杂度为 $O(\log^2V)$。
```cpp
ll cnt,tmp[logV];
void pre(){
cnt=0;
for(int i=0;i<logV;++i){
for(int j=i-1;j>=0;--j)if(a[i]&(1ll<<j))a[i]^=a[j];
if(a[i])tmp[cnt++]=a[i];
}
}
```
依旧先判断是否存在 $0$。然后从高到低扫过每个有值的 $a_i$。根据前面的内容，我们可知如果异或上它，结果的排名就在前一半，否则就在后一半。于是我们就能求第 $k$ 小了。
要先运行 $\operatorname{pre}()$ 函数，单个 $\operatorname{kth}(k)$ 的时间复杂度 $O(\log V)$。
```cpp
ll kth(ll k){
k-=flag0;
if(!k)return 0;
if(k>=(1ll<<cnt))return-1;
ll r=0;
for(int i=0;i<cnt;++i)if(k&(1ll<<i))r^=tmp[i];
return r;
}
```
---
### 异或和排名
注意也是去重后的排名。
要先运行 $\operatorname{pre}()$ 函数，单个 $\operatorname{rk}(k)$ 的时间复杂度 $O(\log V)$。
```cpp
ll cnt,tmp[logV];
void pre(){
cnt=0;
for(int i=0;i<logV;++i){
for(int j=i-1;j>=0;--j){
if(a[i]&(1ll<<j))a[i]^=a[j];
}
if(a[i])tmp[++cnt]=i; //注意这里的tmp我只存了最高位
}
}
ll rk(ll x){
ll r=flag0;
for(int i=cnt;i;--i)if(x&(1ll<<tmp[i]))r+=(1ll<<(i-1));
return r;
}
```
---
### [P4869 albus就是要第一个出场](https://www.luogu.com.cn/problem/P4869)
给定 $n$ 个数 $a_i$ 和一个数 $C$，求所有子集（包含空集）异或和**不去重**并从小到大排序，记作 $S$，求 $C$ 在 $S$ 中的（最小）下标，对 $10086$ 取模。
$n\leq10^5,V\leq10^9$。
---
结论：设线性基的秩为 $cnt$，对于 $2^{cnt}$ 个能组出的不同元素，每个在 $S$ 中的数量相同，为 $2^{n-cnt}$。
对于线性基之外的元素，有 $2^{n-cnt}$ 个任意子集，每个的异或和都可以再通过线性基组出 $x$，那么 $x$ 的出现次数即为 $2^{n-cnt}$（只用线性基中元素相当于线性基外的为空集）。
时间复杂度 $O(n\log V+\log^2V)$。
```cpp
for(int i=1;i<=n;++i){
ll x=in();
L.insert(x);
}
L.pre();
ll r=L.rk(C); //注意本题rk函数不要初始化r=flag0
for(int i=1;i<=n-L.cnt;++i)r=r*2%10086;
printf("%lld",(r+1)%10086);
```
# Part.3 线性基建模
*光说不练假把式，来多看几道线性基题目。*
---
### [P15096 [ICPC 2025 LAC] Brazilian FootXOR](https://www.luogu.com.cn/problem/P15096)
有 $n$ 个人，每个人的能力为长度为 $m$ 的二进制数，要求挑出 $k$ 个人分为一组，再挑 $k$ 个人分为另一组，满足两组人异或和相同，不存在满足的方案输出`*`。
$n,m\leq1.5\times10^3$。
---
两组人异或和相同，说明这 $2k$ 个人异或和为 $0$，反之也成立。故转化为挑出偶数个数使得其异或和为 $0$。
可以使用线性基解决，保证偶数的方法是给每个人的二进制数后面再加一个 $1$，这样异或和为 $0$ 保证有偶数个人。时间复杂度为 $O(\frac{nm}{w})$。
::::success[code]
```cpp
struct Linear_Basis{
bitset<N>a[N],b[N]; //b表示基中元素由那些人异或而来,用于输出,而非线性基
bool flag0;
bitset<N>insert(bitset<N>&x,int idx){
bitset<N>r;r[idx]=1;
for(int i=0;i<=k;++i){
if(x[i]){
if(a[i][i])x^=a[i],r^=b[i];
else{
a[i]=x,b[i]=r;
return r;
}
}
}
flag0=1;
return r;
}
}L;
//假设现在新增的数为x
x[m]=1; //新增一位为1
y=L.insert(x,i); //输入的数在基中被表示的情况
if(L.flag0){
int cnt=0;
for(int i=1;i<=n;++i){
if(y[i])printf("%d",((++cnt)&1)?1:2);
else printf("0");
}
return 0;
}
```
::::
---
### [P17127 [ICPC 2025 Shanghai R] Gemcrate](https://www.luogu.com.cn/problem/P17127)
$n$ 个数 $a_i$，进行分组，最大化每组异或和的按位与和。
$n\leq5\times10^5,V\leq2^{60}$。
---
显然至多分两组，否则三组合并成一组结果不变。
记 $\oplus_{i=1}^na_i=s$。分一组结果为 $s$，分两组则结果为 $x\&(x\oplus s)$，考虑将 $a_i$ 与上 $s$ 取反的结果加入线性基求一个最大值。
时间复杂度 $O(n\log V)$。
---
### [P4151 [WC2011] 最大 XOR 和路径](https://www.luogu.com.cn/problem/P4151) / [CF845G Shortest Path Problem?](https://www.luogu.com.cn/problem/CF845G)
给定一张 $n$ 个点 $m$ 条边的带权无向连通图，求 $1$ 号点到 $n$ 号点的（非简单）路径异或和最大 / 小值。
$n\leq5\times10^4,m\leq10^5,V\leq10^{18}$。
---
考虑求一个生成树，对于点 $u$ ，其到 $1$ 号点的树边异或和为 $d_u$。对于所有非树边 $(u,v)$，它都对应着一个环 $u\rightarrow1\rightarrow v\rightarrow u$，其权值为 $d_u\oplus d_v\oplus w_{u\rightarrow v}$，发现仅使用这些环，能够线性组合出其它的环，因为走过一条边两次相等于没有走。
将上述所有非树边所对的环加入线性基，最后答案为 $d_n$ 在线性基中的最大 / 小表示。
时间复杂度 $O(m\log V)$。
```cpp
vector<pair<int,ll>>e[N];
void dfs(int u){
vst[u]=1;
for(int i=0;i<e[u].size();++i){
int v=e[u][i].first;ll w=e[u][i].second;
if(vst[v])L.insert(d[u]^d[v]^w);
else{
d[v]=d[u]^w;
dfs(v);
}
}
}
```
---
### [P14994 异或最短路和](https://www.luogu.com.cn/problem/P14994)
给定一张 $n$ 个点 $m$ 条边的带权无向图，求对于每个有序点对之间（非简单）路径异或和最小值之和：
$$\sum_{u=1}^n\sum_{v=1}^n\operatorname{dist}(u,v)$$
若 $u,v$ 无法互达，$\operatorname{dist}(u,v)=0$。
$n,m\leq2\times10^5,V\leq10^{18}$。
---
[题解链接](https://www.luogu.com.cn/article/lydm4eyf)。
若 $u,v$ 可达，则 $\operatorname{dist}(u,v)$ 是 $d_u\oplus d_v$ 在该连通块中所有环构成的线性基中的最小表示。考虑快速计算。
介绍一个性质，假设 $f(x)$ 为 $x$ 在线性基的最小表示， 那么有：
$$f(x\oplus y)=f(x)\oplus f(y)$$
按位考虑，分类讨论易证。
那么原式可以按位计算，时间复杂度 $O((n+m)\log V)$。
```cpp
for(int k=0;k<vec.size();++k){ //枚举连通块内的点
int i=vec[k];
f[i]=L.minrep(d[i]);
for(int j=0;j<V;++j)if(f[i]&(1ll<<j))++c[j]; //统计每一位1的个数
}
for(int k=0;k<vec.size();++k){
int i=vec[k];
for(int j=0;j<V;++j){
if(f[i]&(1ll<<j))ans=(ans+(1ll<<j)*(vec.size()-c[j])%mod)%mod;
else ans=(ans+(1ll<<j)*c[j]%mod)%mod;
}
}
```
---
### [AT_abc451_g [ABC451G] Minimum XOR Walk](https://www.luogu.com.cn/problem/AT_abc451_g)
给定一张 $n$ 个点 $m$ 条边的带权无向连通图，求点对 $(u,v)$ 的（非简单）路径异或和最小值小于等于 $k$ 的数量。
$n,m\leq2\times10^5,V\leq2^{30}$。
---
赛时紧张使用 memset 导致 TLE 2 个点，遗憾离场。有幸写过 [题解](https://www.luogu.com.cn/article/20tlfmjk)。
接着上题，设 $d_u$ 在线性基中的最小表示为 $f_u$，现在求 $f$ 中有多少点对 $(u,v)$ 满足 $f_u \oplus f_v \leq k$。
我们可以通过将所有 $f_u$ 依次插入一棵二进制 Trie树，并在插入前查询当前树中有多少数与 $f_u$ 的异或值 $\leq k$ 来实现。
总之想讲的是处理异或的工具除了线性基，还有 01 Trie，思维不要太死。
时间复杂度 $O((n+m)\log V)$。
::::success[code]
这是赛时代码，以前马蜂还挺宽松的......
```cpp
struct linearbasis{ //线性基
int bs[B];
linearbasis(){ memset(bs,0,sizeof(bs)); }
void insert(int x) {
for(int i = B - 1;i >= 0;--i){
if((x >> i) & 1){
if(!bs[i]){
bs[i] = x;
break;
}
x ^= bs[i];
}
}
}
int query(int x){
for(int i = B - 1;i >= 0;--i){
if(((x>>i)&1) && bs[i])x ^= bs[i];
}
return x;
}
};
int n,m,k,tot;
struct trie{
int cnt[N * B];
int ch[N * B][2];
void clear(){
for(int i = 0;i <= tot;++i)cnt[i] = ch[i][0] = ch[i][1] = 0;
//我这辈子再也不用memset了,就差1分钟就AK了
tot = 0;
}
void add(int v){
int x = 0;
for(int i = B - 1;i >= 0;--i){
int f = (v>>i)&1;
if(!ch[x][f])ch[x][f]= ++tot;
x = ch[x][f];
cnt[x]++;
}
}
int query(int v,int k){
int x = 0;
int res = 0;
for(int i = B - 1;i >= 0;--i){
int bx = (v>>i)&1,bk = (k>>i)&1;
if(bk){
int z = ch[x][bx];
if(z)res += cnt[z];
x = ch[x][bx ^ 1];
}
else x = ch[x][bx];
if(!x)break;
}
if(x)res += cnt[x];
return res;
}
}T;
vector<pair<int,int>>g[N];
struct edge{ int u,v,w; };
vector<edge>nt;
int d[N],vst[N],f[N];
queue<int>q;
long long solve(){
n = in(),m = in(),k = in();
for(int i = 1;i <= n;++i)g[i].clear(),d[i] = -1;
nt.clear();
for(int i = 1;i <= m;++i){
int u = in(),v = in(),w = in();
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i = 1;i <= n;++i)vst[i] = 0;
q.push(1);
d[1] = 0;
vst[1] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = 0;i < g[u].size();++i){
int v = g[u][i].first,w = g[u][i].second;
if(!vst[v]){
d[v] = d[u] ^ w;
vst[v] = 1;
q.push(v);
}
else if(u < v)nt.push_back({u,v,w});
}
}
linearbasis L;
for(int i = 0;i < nt.size();++i)L.insert(d[nt[i].u] ^ d[nt[i].v] ^ nt[i].w);
for(int i = 1;i <= n;++i)f[i] = L.query(d[i]);
T.clear();
long long res = 0;
for(int i = 1;i <= n;++i){
res += T.query(f[i],k);
T.add(f[i]);
}
return res;
}
```
::::
# Part.4 线性基进阶
*本版块介绍线性基的拓展功能，有一定难度。*
---
### 线性基求并
假设现在有两个线性空间 $V_1$ 和 $V_2$，线性基分别为 $B_1$ 和 $B_2$，求并集 $V_0=V_1\cup V_2$ 的线性基 $B_0$。
很简单，直接将 $B_2$ 中的数全部插入到 $B_1$ 中即可得到 $B_0$，建议使用结构体封装。
需要插入 $O(\log V)$ 个数，单次插入时间复杂度为 $O(\log V)$，故总复杂度为 $O(\log^2V)$。
```cpp
Linear_Basis merge(Linear_Basis B1,Linear_Basis B2){
Linear_Basis B0=B1;
for(int i=0;i<logV;++i)if(B2.a[i])B0.insert(B2.a[i]);
return B0;
}
```
---
### 线性基求交
参考 yuanquming 大神的 [博客](https://www.cnblogs.com/yuanquming/p/11260668.html)。我并没有很好地理解他的表述（我太菜了），这绝对是本篇文章最难的部分之一，但现归纳成个人认为较容易理解的内容。
假设现在有两个线性空间 $V_1$ 和 $V_2$，线性基分别为 $B_1$ 和 $B_2$，求交集 $V_0=V_1\cap V_2$ 的线性基。
**引理**：记 $S=V_1\cap B_2,T=B_2 \setminus S$，若 $B_1\cup T$ 线性无关，则 $S$ 是 $V_0$ 的一组基，即 $\operatorname{span}(S)=V_0$。
证明：
>证明显然分为两部分，证明 $S$ 不能线性组合出 $(V_1\cup V_2) \setminus V_0$ 的任意元素，并且能线性组合出所有 $V_0$ 的元素。
>
>第一部分反证法易证，假设 $v\in V_1\setminus V_0$，且 $S$ 能线性表示 $v$，则说明 $B_2$ 也能线性表示 $v$，故 $v\in V_2$，与假设不符，另一种情况类似。
>
>第二部分也使用反证法，假设 $v\in V_0$ 且不能被 $S$ 线性表示。因为 $v\in V_2$，$v$ 能被 $B_2=S\cup T$ 线性表示，又因为 $S$ 不能线性组合出 $v$，故 $T$ 中元素系数不全为 $0$。
>
>而 $S\subseteq V_1$，则 $S$ 中所有元素都能被 $B_1$ 线性组合出。将 $S\cup T$ 线性表示的方式中 $S$ 全部用 $B_1$ 线性表示，则 $v$ 既能被 $B_1$ 线性表示，也能被 $B_1\cup T$ 线性表示，作差得到 $B_1\cup T$ 能够线性表示 $0$ 并且 $T$ 中有系数不为 $0$，则 $B_1\cup T$ 线性相关，与假设不符。
至此，我已花费一天。然而实际情况中，$B_1\cup T$ 可能线性相关（哭）。
我们需要构造一组基 $B_2'$，使得 $B_1\cup T'$ 线性无关。
定义：
* $B_2'$ 需要动态构造的基，初始为空。
* $S'=V_1\cap \operatorname{span}(B_2')
-
T'=B_2'\setminus S'
-
- 对于 B_0 的每一个向量 v_i，假设 X\subseteq V_1,Y\subseteq \operatorname{span}(B_0)\setminus V_1，则对于 v_i=X\oplus Y，其在 V_1 上的“分量” P_i=\oplus_{x\in X}x。
我们只用维护这些，并先初始化为：
-
S'=\emptyset
-
B_0=B_1
-
P=B_1
至于别的为什么不用维护，看算法流程后应该就能明白。
依次插入 B_2 中的所有元素，假设现在插入 x\in B_2，尝试用 B_0 去线性表示 x：
- 如果 x 不能被 B_0 线性表示，说明它不可能作为交集的基出现，x 要插入 B_0（理论上是 B_2' 的 T'），同时记录 P。
- 否则，x 一定能被 B_1\cup T' 用唯一方式表示，设 x=X\oplus Y，其中 X\subseteq V_1 且 Y\subseteq\operatorname{span}(T')，X 是 x 在 V_1 中的分量，可以通过 P 计算，最后在 S' 中加入 X。
上述流程中我们定义的所有内容时刻成立，并且最后保证 \operatorname{span}(B_2')=\operatorname{span}(B_2)=V_2。
时间复杂度 O(\log^2V)。
Linear_Basis intersect(Linear_Basis B1,Linear_Basis B2){
Linear_Basis B0=B1,S;int P[logV];
for(int i=0;i<logV;++i)S.a[i]=0,P[i]=B1.a[i];
for(int i=0;i<logV;++i){
ll x=B2.a[i],X=0;if(!x)continue;
for(int j=i;j>=0;--j){
if(x&(1ll<<j)){
if(B0.a[j]){
x^=B0.a[j],X^=P[j];
if(x)continue;
S.a[i]=X;
}
else B0.a[j]=x,P[j]=X;
break;
}
}
}
return S;
}
呕心沥血才一知半解（哭）。
最大权和线性基 / P4301 [CQOI2013] 新Nim游戏 / P4570 [BJWC2011] 元素 / P3265 [JLOI2015] 装备购买
给定 n 个数，有数值 a_i 和权值 v_i，从中挑出一些，使得 a_i 线性无关，并且最大化它们的权和 v_i。
---
贪心，将 $v_i$ 从大到小排序，依次将 $a_i$ 插入到线性基中，如果线性基能够表示 $a_i$，即加入 $a_i$ 会让异或和等于 $0$，就不选 $a_i$；否则将 $a_i$ 加入线性基。
**最大权和线性基**，是线性拟阵的最大权独立集。严谨证明贪心法的正确性自然需要使用**拟阵**（Matroid）。我会再出一篇文章简要介绍拟阵的（逃）。
时间复杂度 $O(n\log n+n\log V)$。
```cpp
struct item{ ll a,v; }it[N];
bool cmp(item x,item y){ return x.v>y.v; }
sort(it+1,it+1+n,cmp);
for(int i=1;i<=n;++i){
if(!L.check(it[i].a)){
L.insert(it[i].a);
ans+=it[i].v;
}
}
printf("%lld",ans);
```
# Part.5 数据结构
*接下来浅浅讲一下关于线性基的一些数据结构（逃）。线性基在代码层面就是一个很小的数组，并且支持合并，所以线段树那一套都可以用来维护线性基。*
---
### [P4839 P 哥的桶](https://www.luogu.com.cn/problem/P4839)
一个长为 $n$ 的序列，询问区间线性基，动态修改（没有删除）。
$n\leq5\times10^4,V\leq2^{30}$。
---
线性基可以合并，但是复杂度较大，为 $O(\log^2V)$，再加上线段树需要合并 $O(\log n)$ 就为 $O(\log n\log^2V)$。
---
### [P15044 [UOI 2022 II Stage] 树](https://www.luogu.com.cn/problem/P15044)
[P4839 P 哥的桶](https://www.luogu.com.cn/problem/P4839) 的树上版本，询问子树元素所有子集异或和去重后的第 $k$ 大元素。
---
[题解链接](https://www.luogu.com.cn/article/f6w3zszp)。
树剖即可，时间复杂度 $O((n+q)\log n\log^2V)$。
---
### 前缀线性基
[P4839 P 哥的桶](https://www.luogu.com.cn/problem/P4839) 的静态版本。
---
如果要求更快，静态场景可以使用 [猫树分治](https://oi-wiki.org/ds/cat-tree/)，只用单次合并，能做到单次查询 $O(\log^2V)$。
但是使用**前缀线性基**可以做到单次查询 $O(\log V)$。
具体地我们维护 $[1,i]$ 范围的线性基，对于每个线性基元素 $a_i$，记录其出现位置 $p_i$，插入时将新的基底换掉老的基底即可。查询时只允许使用 $p_i$ 合法的基底。
```cpp
int p[N];
void insert(ll x,int idx){
for(int i=logV-1;i>=0;--i){
if(!(x&(1ll<<i)))continue;
if(!a[i]){a[i]=x,p[i]=idx;return;}
if(p[i]<idx)swap(a[i],x),swap(p[i],idx);
x^=a[i];
}
flag0=1;
}
Linear_Basis L[N];
for(int i=1;i<=n;++i){
L[i]=L[i-1];
L[i].insert(a[i],i);
}
```
---
### [P3292 [SCOI2016] 幸运数字](https://www.luogu.com.cn/problem/P3292)
给定一棵 $n$ 个点的树和点权 $g_u$，对于 $q$ 组问询，在 $u$ 到 $v$ 的唯一路径上选择任意个点，最大化点权异或和。
$n\leq2\times10^4,q\leq2\times10^5,V\leq2^{60}$。
---
参考前缀线性基，我们可以拓展到树上，预处理每个点到根节点的线性基，并且让高位基底的深度尽量深。
回答问询 $(u,v)$ 时，只使用 $u,v$ 线性基中深度大于等于 $lca(u,v)$ 的即可，具体地，合并这两个线性基即可。
预处理 $lca$ 和线性基为 $O(n\log n+n\log V)$，每次问询需要查询 $lca$ 并且线性基合并，为 $O(q\log n+q\log^2V)$。总复杂度加起来为 $O(n\log n+n\log V+q\log n+q\log^2V)$。
::::success[code]
额，没空再写一遍了，这是一年前的代码，凑活着看吧。
```cpp
struct linear_basis{
#define V 60
long long lb[V + 1];
int pos[V + 1];
void insert(int w){
long long x = g[w];
if(!x)return;
for(register int i = V;i >= 0;--i){
if(x>>i&1){
if(lb[i]){
if(dpt[w] > dpt[pos[i]])swap(pos[i],w),swap(lb[i],x);
x ^= lb[i];
}
else{
pos[i] = w;
lb[i] = x;
return;
}
}
}
}
#undef V
}a[N];
void dfs(int u,int f){
dpt[u] = dpt[f] + 1;
fa[u][0] = f;
for(register int i = 1;i < A;++i)fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(register int i = 0;i <= 60;++i)a[u].pos[i] = a[f].pos[i],a[u].lb[i] = a[f].lb[i];
a[u].insert(u);
for(register int i = 0;i < e[u].size();++i){
int v = e[u][i];
if(v != f)dfs(v,u);
}
}
int lca(int u,int v){
if(dpt[u] < dpt[v])swap(u,v);
for(register int i = A - 1;i >= 0;i--){
if(dpt[fa[u][i]] >= dpt[v])u = fa[u][i];
}
if(u == v)return u;
for(register int i = A - 1;i >= 0;i--){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
dfs(1,0);
while(q--){
int u = in(),v = in();
int l = lca(u,v);
for(register int i = 60;i >= 0;--i){
if(dpt[a[u].pos[i]] >= dpt[l])b[i] = a[u].lb[i];
else b[i] = 0;
}
for(register int i = 60;i >= 0;--i){
if(dpt[a[v].pos[i]] >= dpt[l]){
long long x = a[v].lb[i];
if(x){
for(register int j = i;j >= 0;--j){
if((x>>j)&1){
if(!b[j]){
b[j] = x;
break;
}
x ^= b[j];
}
}
}
}
}
long long ans = 0;
for(register int i = 60;i >= 0;--i)ans = max((ans ^ b[i]),ans);
printf("%lld\n",ans);
}
```
::::
---
### 随机增删线性基
删除对于线性基来说是很严重的，因为有的元素可能插入成功，有的可能没有影响。
按照前缀线性基的思想，离线后将时间视为序列，每个数就变为一段区间，设每个 $a_i$ 的删除时间为 $t_i$ ，插入时让存活时间更久的元素占据高位，查询时只要判断一下 `t[i]>tim` 即可，时间复杂度不变，仍然为 $O(n\log V)$。
```cpp
int t[N];
void insert(ll x,int tim){
for(int i=logV-1;i>=0;--i){
if(!(x&(1ll<<i)))continue;
if(t[i]<tim)swap(tim,t[i]),swap(x,a[i]);
if(tim)x^=a[i];
else return;
}
flag0=1;
}
```
也可以使用**线段树分治**，为半在线做法，时间复杂度 $O(n\log n\log V)$。
完全的在线做法是维护每个基中元素是由哪些原始元素异或组合而来，删除基中元素时找某个非基元素用它表示，替入基中，再消除其影响。实现繁琐，复杂度高，常数巨大，竞赛不用。
---
### [P3733 [HAOI2017] 八纵八横](https://www.luogu.com.cn/problem/P3733)
给定 $n$ 个点 $m$ 条边的带权无向图，动态加边删边、修改边权，保证互通，每次问询求从 $1$ 出发，最后回到 $1$ 的一条非简单路径，最大化异或和。
$n,m\leq5\times10^2,q\leq10^3,d\leq10^3$，$d$ 表示布尔向量长度。
---
依旧跑一棵生成树，定义 $1$ 到 $u$ 的异或和为 $d_u$，那么对于非树边 $(u,v)$ 构成的环权值已经讲过，插入线性基以查询最大值即可。
至于动态，使用可删除线性基，时间复杂度 $O(n+(m+q)\frac{d^2}{w})$，使用 bitset，其中 $w=64$。