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\)。

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 【模板】线性基。

首先构造出这个序列的线性基。

接着采取贪心的思想，从线性基的最高位开始，若当前的答案异或线性基的这个元素可以变得更大，那么就异或它。答案的初值为 \(0\)。

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}\)）。

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\)（二者只能加入其一）加入答案的线性基中。

由于有复制操作，为方便，使用结构体。

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\) 表示这个元素的最晚删除时间。

插入

与不带删除的线性基基本类似。根据贪心思想，我们希望能使高位基的删除时间较晚（否则，到了删除时间，高位基无法选择，会使答案变劣）。

因此，从插入的数的高位开始枚举，能插就插。

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];
        }
}

求最大值

这里的“最大值”含义上文已有描述，故不再过多赘述。

只需在不带删除的线性基的基础上加上一个关于时间的特判。

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]元素

算法分析：线性基，排序，贪心。

首先按照矿石的 \(\text{Magic}\) 值降序排序，接着把元素的编号扔到线性基里面去。如果 \(\text{Number}_i\) 能加入线性基，则将 \(ans\) 加上 \(\text{Magic}_i\)。

#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]彩灯

算法分析：线性基，字符串。

这是一题很明显的线性基，由于线性基可以通过异或的方式，得到原序列中的任意元素，所以我们只要直接求线性基就可以了。设线性基的长度为 \(ans\)，则答案为 \(2^{ans} \bmod 2008\)。

#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 游戏

算法分析：线性基，排序，博弈论。

显然，根据小学奥数知识根据 Nim 游戏的结论，不能给后手任何让石子数异或为 \(0\) 的机会，所以在插入前先询问该数是否会让石子异或和变为 \(0\)，若会，则把这堆石子拿掉，否则加入线性基里，这样后手无论如何都不能让石子异或和变为 \(0\)。值得吐嘈的是，先手必胜，所以输出 \(-1\) 是没分的。

关于最小值的问题，跟例一一样，先排序即可。

#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 和路径

算法分析：线性基，图形结构，DFS。

先假设选择了一条从 \(1\) 到 \(n\) 的主路径，然后在这条路径上向外拓展。显然，只有环对答案有影响，因为非环的边一定会走两次，异或和为 \(0\)。

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

如何找环？其实很简单，通过在 DFS 树上通过返祖边找到简单环的方法，很容易能找到环。

#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] 八纵八横

算法分析：线性基，图形结构，DFS，bitset。

参考例四的思路，只有环上边能对答案做出贡献。因此通过 DFS 找返祖边搜环，扔进线性基里去，找到最大值即可。

注意到含有删除操作。因此把操作离线掉，之前介绍的带删除线性基派上了用场。

另外一个需要注意的点是，经济影响因子的二进制最大长度为 \(10^3\)，因此常规的线性基无法通过本题，需要改用 bitset。

据说有在线做法？srds 笔者太菜了不会。（悲

#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、线性基习题

限于篇幅，恕不赘述。

笔者找到了一个题单，里面的习题还是挺全的，就放在这里了。

10、结语

参考资料：

• 线性基详解

• 线性基求交与求并

• 男默女泪！线性基求交全网最通俗解释

• [WC2011] 最大XOR和路径 题解

• [HAOI2017] 八纵八横 题解

转载