【学习笔记】浅谈异或线性基
RP_INT_MAX
2022-08-11 20:31:27
## 1、前言
Upd on 2022.8.19：添加线性基的求交与求并。
Upd on 2023.5.9：日报过审，于是修了格式，改了一些以前写的~~过于迷惑的语言表述~~。
Upd on 2023.5.12：采纳魏老师建议，添加带删除线性基部分，同时增加一道例题。
------
线性基作为一个工具，在很多跟异或有关的题目中都有广泛的应用。
提前介绍一个异或（用 $\oplus$ 表示）的性质。
若 $a\oplus b\oplus c=0$，则 $a\oplus b=c$。
因此，若 $a\oplus b=c$，则 $a\oplus c=b$。
## 2、线性基基本概念
**定义**：给定数集 $S$，以异或运算张成的数集与 $S$ 相同的极大线性无关集，称为原数集的一个线性基。
通俗地说，线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。
## 3、线性基重要性质
### 性质一
原序列的任意一个数都可以由线性基内部的一些数异或得到。
### 性质二
线性基内部的任意数异或起来都不能得到 $0$。
### 性质三
线性基内部的数个数唯一；且在保持性质一的前提下，数的个数是最少的。
------
下面给出三个性质的证明。
### 性质二
用反证法，设 $d_i\oplus d_j\oplus d_k=0$（$d_k$ 比 $d_i,d_j$ 更晚插入线性基），则 $d_i\oplus d_j=d_k$。由于$d_k$ 能由 $d_i\oplus d_j$ 得到，故 $d_j$ 不能进入线性基。
故假设不成立，线性基中不存在任何数异或起来可以得到 $0$。
证毕。
### 性质一
对将插入的数 $x$ 分类讨论。
$x$ 不能成功插入线性基时，显然 $x$ 异或上线性基中的若干个数的结果为 $0$。那么就能得到：$x\oplus d_i\oplus d_j\oplus d_k\oplus \dots=0$，则有：$d_i\oplus d_j\oplus d_k\oplus \dots=x$。所以，若 $x$ 不能成功插入线性基，是因为当前线性基里面的一些数异或的结果等于 $x$。
$x$ 可以成功插入线性基时，设 $x$ 插入到了线性基的第 $i$ 个位置。显然，插入前可能异或若干个数，则有 $x\oplus d_a\oplus d_b\oplus d_c\oplus \dots=d_i$，那么 $d_i\oplus d_a\oplus d_b\oplus d_c\oplus \dots=x$。所以 $x$ 也可以由线性基里面的若干个数异或得到。
综上，原序列的任意一个数都可以由线性基内部的一些数异或得到。
证毕。
### 性质三
若序列里面的所有元素都可以插入到线性基里面，则不管用什么顺序将序列里的数插入线性基，线性基中的元素一定与原序列元素数量相同。
若序列里面的一些元素不能插入到线性基里面，则设 $x$ 不能插入线性基，一定满足形如 $d_i\oplus d_j\oplus d_k=x$ 的式子。尝试将插入顺序改变为 $d_i,d_j,x,d_k$，则 $d_k$ 就不可能插入成功，原因很简单，留给读者自己思考。
通俗地说，原来是 $x$ 插不进去，改变顺序后，则是 $d_k$ 插不进去。即对于插不进去的元素，改变插入顺序后，要么还是插不进去；要么就是插进去了，同时另一个原来插进去的元素插不进去了。因此，可以插进去的元素数量一定是固定的。
若去掉线性基里面的任一个数，都会使得原序列里的数无法通过用线性基里的元素异或得到，没有多余的元素。所以线性基的元素个数在保持性质一的前提下，一定是最少的。
证毕。
## 4、线性基基本操作
### 插入
设数组 $p$ 表示序列 $\{a_n\}$ 的线性基，待插入数为 $x$，下标从 $0$ 开始。
将 $x$ 转为二进制，从它的高位开始，如果当前位为 $1$，并且线性基 $p$ 的第 $i$ 位上没有数，那就赋成当前值 $x$。否则，将 $x$ 异或 $p_i$。
```cpp
typedef long long ll; //后同
void upd(ll x) {
for(int i=60;i>=0;--i)
if(x>>i&1) {
if(!p[i]) {p[i]=x;break;}
x^=p[i];
}
}
```
### 求最大值
在一个序列 $\{a_n\}$ 中，取若干个数，求它们的最大异或和。事实上，这题就是 [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812)。
首先构造出这个序列的线性基。
接着采取贪心的思想，从线性基的最高位开始，若当前的答案异或线性基的这个元素可以变得更大，那么就异或它。答案的初值为 $0$。
```cpp
ll getmx() {
ll ans=0;
for(int i=60;i>=0;--i)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
```
### 求最小值
如果是求用线性基 $p$ 内的元素能异或出的最小值，那么就是最小的 $p_i$ 了。其正确性显然，因为最小的 $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$ 个元素（注意不是直接异或 $p_{i-1}$）。
```cpp
inline void prework() {
for(int i=1;i<=60;++i)
for(int j=1;j<=i;++j)
if(p[i]&(1LL<<j-1)) p[i]^=p[j-1];
}
inline ll getkth(int k) {
if(k==1&&size<n) return 0;
if(size<n) --k;
//n表示序列长度，size表示线性基内部元素个数
prework();
ll ans=0;
for(int i=0;i<=60;++i)
if(p[i]) {
if(k&1) ans^=p[i];
k>>=1;
}
return ans;
}
```
### 询问存在性
判断数 $x$ 能否被当前线性基中元素异或得到。
把 $x$ 尝试插入进线性基，假如可以插入，说明不能异或得到，假如插不进去，则说明可以异或得到。
代码略。
### 线性基求并
很简单。假设有两个线性基 $A,B$，显然，将 $A$ 的每一个元素插入线性基 $B$ 即可，插不进去则忽略。
代码略。
### 线性基求交
求一个线性基，它一定能被两个线性基 $A,B$ 分别表示。
如果 $B_i$ 能被 $\{A_{i=1\sim x}\}$
与 $B_{j=1\sim i-1}$ 线性表示出来，就把 $\bigoplus_{i=1}^{x}A_i$ 或者 $\bigoplus_{j=1}^{i-1}B_j$（二者只能加入其一）加入答案的线性基中。
由于有复制操作，为方便，使用结构体。
```cpp
struct node {
ll p[60];
node() {memset(p,0,sizeof p);}
};
node d,all;
node merge(const node&a,const node&b) {
node res;
d=a,all=a; //all表示目前所有可用的低位基
ll k; //k是把Bi和它的低位削减至0所用到的A的异或和
for(int i=0;i<60;++i) {
if(!b.p[i]) continue;
ll v=b.p[i];
k=0;
int j;
for(j=i;j>=0;--j)
if(1LL<<j&v) {
if(all.p[j]>0)
v^=all.p[j],k^=d.p[j];
else break;
}
if(!v) res.p[i]=k;
else all.p[j]=v,d.p[j]=k;
}
return res;
}
```
## 5、带删除线性基
采纳魏老师建议，增加此版块。
在线的不太会就不写了，也算是给后人留个坑填嘛（
------
将操作离线，维护 $p_i$ 表示线性基内的第 $i$ 个元素，$t_i$ 表示这个元素的最晚删除时间。
### 插入
与不带删除的线性基基本类似。根据贪心思想，我们希望能使高位基的删除时间较晚（否则，到了删除时间，高位基无法选择，会使答案变劣）。
因此，从插入的数的高位开始枚举，能插就插。
```cpp
void upd(ll x,int time) { //插入数x,该数最晚删除时间为time
for(int i=60;i>=0;--i)
if(x>>i&1) {
if(t[i]<time) {
swap(time,t[i]);
swap(x,p[i]);
}
if(time==0) break;
x^=p[i];
}
}
```
### 求最大值
这里的“最大值”含义上文已有描述，故不再过多赘述。
只需在不带删除的线性基的基础上加上一个关于时间的特判。
```cpp
ll getmx(int time) { //查询当前时间为time时的最大值
ll ans=0;
for(int i=60;i>=0;--i)
if(time<t[i])
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
```
## 6、线性基复杂度
这里介绍一下线性基的复杂度。
### 时间复杂度
插入：`upd()` 函数从 $60$ 循环到 $0$，而 $a_i$ 的值域为 $2^{60}$，故时间复杂度为 $O(\log N)$（$N$ 表示值域，$\log$ 均以 $2$ 为底，下同）。
求最大值：读入数据需要 $O(n)$ 的时间，插入的复杂度上面讲过了，总复杂度为 $O(n\log N)$（$n$ 为原序列长度，下同）。
求最小值：检查需要 $O(n)$ 的时间，加上判断能否插入，总复杂度为 $O(n\log N)$。
求 $k$ 小值：主要是 `prework()` 函数较为耗时。总复杂度为 $O(\log^2N)$。
判断数 $x$ 能否被当前线性基中元素异或得到：也就是尝试插入，复杂度 $O(\log N)$。
求并：很显然，$O(\log^2N)$。
求交：从代码里可看出，两重循环，故也是 $O(log^2N)$。
### 空间复杂度
显然，需要一个构造线性基的辅助数组，空间复杂度为 $O(\log N)$。
## 7、线性基例题
这里，以两道例题，让读者更加熟悉线性基的用法。
以下每一道例题，笔者的讲解都比较简略，故给出完整的参考代码以加深理解。如果读者觉得难以接受，可以参看对应题目的题解。
还是选主题库的题吧，怕被没绑账号的人喷，想要做非主题库题目，可以参考后面给的习题单（
### 例一：[[BJWC2011]元素](https://www.luogu.com.cn/problem/P4570)
算法分析：线性基，排序，贪心。
首先按照矿石的 $\text{Magic}$ 值降序排序，接着把元素的编号扔到线性基里面去。如果 $\text{Number}_i$ 能加入线性基，则将 $ans$ 加上 $\text{Magic}_i$。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
struct node {
ll a;
int b;
friend bool operator< (const node &a,const node &b) {
return a.b>b.b;
}
} a[1010];
ll p[100];
int n,ans;
inline void upd(ll x,int y) {
for(int i=60;~i;--i)
if(x>>i&1) {
if(!p[i]) {p[i]=x,ans+=y;break;}
x^=p[i];
}
}
int main () {
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i].a>>a[i].b;
sort(a+1,a+1+n);
for(int i=1;i<=n;++i) upd(a[i].a,a[i].b);
cout<<ans<<endl;
return 0;
}
```
### 例二：[[TJOI2008]彩灯](https://www.luogu.com.cn/problem/P3857)
算法分析：线性基，字符串。
这是一题很明显的线性基，由于线性基可以通过异或的方式，得到原序列中的任意元素，所以我们只要直接求线性基就可以了。设线性基的长度为 $ans$，则答案为 $2^{ans} \bmod 2008$。
```cpp
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
string s;
ll p[100];
inline void upd(ll x) {
for(int i=60;~i;--i)
if(x&1LL<<i)
if(p[i]) x^=p[i];
else {p[i]=x;break;}
}
int n,m;
int main () {
cin>>n>>m;
while(m--) {
cin>>s;
ll x=0;
for(int i=0;i<n;++i) x|=(ll)(s[i]=='O')<<i;
upd(x);
}
int ans=0;
for(int i=60;~i;--i)
if(p[i]) ++ans;
cout<<(1LL<<ans)%2008;
return 0;
}
```
## 8、线性基扩展应用
有的时候，题目里面不仅仅有线性基，而更是将其与树论、图论等知识结合起来，这就要求我们不仅会理论知识，而且要触类旁通。
下面，给出三道更难的例题。
### 例三：[[CQOI2013] 新 Nim 游戏](https://www.luogu.com.cn/problem/P4301)
算法分析：线性基，排序，博弈论。
显然，~~根据小学奥数知识~~根据 Nim 游戏的结论，不能给后手任何让石子数异或为 $0$ 的机会，所以在插入前先询问该数是否会让石子异或和变为 $0$，若会，则把这堆石子拿掉，否则加入线性基里，这样后手无论如何都不能让石子异或和变为 $0$。值得吐嘈的是，先手必胜，所以输出 $-1$ 是没分的。
关于最小值的问题，跟例一一样，先排序即可。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,a[110],b[110];
ll s,ans;
int main () {
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],s+=1LL*a[i];
sort(a+1,a+1+n);
for(int i=n;i;--i) {
int t=a[i];
for(int j=30;~j;--j)
if(a[i]>>j&1)
if(b[j]) a[i]^=b[j];
else {b[j]=a[i];break;}
if(a[i]) ans+=1LL*t;
}
cout<<s-ans;
return 0;
}
```
### 例四：[[WC2011]最大 XOR 和路径](https://www.luogu.com.cn/problem/P4151)
算法分析：线性基，图形结构，DFS。
先假设选择了一条从 $1$ 到 $n$ 的主路径，然后在这条路径上向外拓展。显然，只有环对答案有影响，因为非环的边一定会走两次，异或和为 $0$。
因为图是联通的，所以可以经过任意环，把所有的环的异或值扔到线性基里，然后再考虑选择哪一条路径。注意到，若从 $1$ 到 $n$ 有多条路径，其实这些路径也构成了环，也会被加入到线性基里，这时候随便选一条路径即可。
如何找环？其实很简单，通过在 DFS 树上通过返祖边找到简单环的方法，很容易能找到环。
```cpp
#include<iostream>
using namespace std;
typedef long long ll;
int hd[100010],num;
struct node {
int next,to;
ll v;
} edg[200010];
inline void add(int fr,int to,ll v) {
edg[++num].to=to;
edg[num].v=v;
edg[num].next=hd[fr];
hd[fr]=num;
}
ll b[100];
inline void upd(ll x) {
for(int i=60;~i;--i)
if(x&1LL<<i)
if(b[i]) x^=b[i];
else {b[i]=x;break;}
}
ll d[50010];
bool vis[50010];
void DFS(int x) {
vis[x]=1;
for(int i=hd[x];i;i=edg[i].next) {
int v=edg[i].to;
if(vis[v]) upd(d[v]^edg[i].v^d[x]);
else d[v]=d[x]^edg[i].v,DFS(v);
}
}
int n,m;
int main () {
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;++i) {
ll x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,z);
}
DFS(1);
ll ans=d[n];
for(int i=60;~i;--i)
if((ans^b[i])>ans) ans^=b[i];
cout<<ans<<endl;
return 0;
}
```
### 例五：[[HAOI2017] 八纵八横](https://www.luogu.com.cn/problem/P3733)
算法分析：线性基，图形结构，DFS，bitset。
参考例四的思路，只有环上边能对答案做出贡献。因此通过 DFS 找返祖边搜环，扔进线性基里去，找到最大值即可。
注意到含有删除操作。因此把操作离线掉，之前介绍的带删除线性基派上了用场。
另外一个需要注意的点是，经济影响因子的二进制最大长度为 $10^3$，因此常规的线性基无法通过本题，需要改用 bitset。
据说有在线做法？srds 笔者太菜了不会。（悲
```cpp
#include <bitset>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1010;
typedef bitset<N> BT;
inline void in(BT &x) {
string s;
cin>>s;
BT tmp(s);
x=tmp;
}
inline void out(BT x) {
bool flag=0;
for(int i=999;i>=0;--i) {
if(x[i]||flag) putchar('0'+x[i]);
if(x[i]) flag=1;
}
if(!flag) putchar('0');
putchar('\n');
}
int tot,hd[N];
struct node {
int next,to;
BT v;
} edg[N];
inline void add(int fr,int to,BT v) {
edg[++tot].to=to;
edg[tot].v=v;
edg[tot].next=hd[fr];
hd[fr]=tot;
}
BT p[N];
int t[N];
void upd(BT x,int time) {
for(int i=1000;i>=0;--i)
if(x[i]) {
if(t[i]<time) swap(time,t[i]),swap(x,p[i]);
if(time==0) break;
x^=p[i];
}
}
void getmx(int time) {
BT ans;
for(int i=1000;i>=0;--i)
if(time<t[i]&&!ans[i]) ans^=p[i];
out(ans);
}
BT dis[N];
bool vis[N];
void DFS(int x) {
vis[x]=1;
for(int i=hd[x];i;i=edg[i].next) {
int v=edg[i].to;
if(vis[v]) upd(dis[v]^edg[i].v^dis[x],0x3f3f3f3f);
else dis[v]=dis[x]^edg[i].v,DFS(v);
}
}
int n,m,q,qcnt,ed[N],op[N],del[N];
BT val[N];
pair<int,int>New[N];
int main () {
ios::sync_with_stdio(0);
cin>>n>>m>>q;
int num=q+1;
for(int i=1;i<=m;++i) {
int u,v;
BT w;
cin>>u>>v,in(w);
add(u,v,w),add(v,u,w);
}
DFS(1);
for(int i=1;i<=q;++i) {
string s;
cin>>s;
int x,y;
BT z;
if(s=="Add") {
cin>>x>>y,in(z);
op[i]=++qcnt;
val[qcnt]=(z^dis[x]^dis[y]);
New[qcnt]=make_pair(x,y);
del[qcnt]=qcnt;
}
else if(s=="Change") {
cin>>x,in(z);
ed[del[x]]=i;
op[i]=--num;
val[num]=(z^dis[New[x].first]^dis[New[x].second]);
del[x]=num;
}
else if(s=="Cancel") {
cin>>x;
ed[del[x]]=i;
}
}
for(int i=1;i<=q;++i)
if(!ed[i]) ed[i]=0x3f3f3f3f;
getmx(0);
for(int i=1;i<=q;++i) {
if(op[i]) upd(val[op[i]],ed[op[i]]);
getmx(i);
}
return 0;
}
```
## 9、线性基习题
限于篇幅，恕不赘述。
笔者找到了一个[题单](https://www.luogu.com.cn/training/11251)，里面的习题还是挺全的，就放在这里了。
## 10、结语
参考资料：
- [线性基详解](https://blog.csdn.net/a_forever_dream/article/details/83654397)
- [线性基求交与求并](https://blog.csdn.net/demon_rieman/article/details/88830846)
- [男默女泪！线性基求交全网最通俗解释](https://absoler.github.io/2020/04/30/%E7%94%B7%E9%BB%98%E5%A5%B3%E6%B3%AA%EF%BC%81%E7%BA%BF%E6%80%A7%E5%9F%BA%E6%B1%82%E4%BA%A4%E5%85%A8%E7%BD%91%E6%9C%80%E9%80%9A%E4%BF%97%E8%A7%A3%E9%87%8A/)
- [[WC2011] 最大XOR和路径 题解](https://www.cnblogs.com/ZJXXCN/p/13093477.html)
- [[HAOI2017] 八纵八横 题解](https://www.luogu.com.cn/blog/Troverld/solution-p3733)
------
另外，感谢魏老师对本文的审核，并提出了意见。
由于笔者很菜，所以本文可能有一些不妥之处，请各路神犇看到后在评论区加以指正。
就此搁笔。希望你在阅读本文以后对线性基有所了解。