线性代数里的数据结构——线性基

定义

在线性代数中我们知道了可以通过高斯消元来求解一个线性空间里面的线性基，那么我们此处考虑一个线性空间只包含若干个数，并且运算是在 $\bmod \ 2$ 下进行的，也就是说加法就是异或操作，这个线性基我们可以发现很多性质。

并且表出的系数必须是 $0$ 或者 $1$，不能是其它实数。

构造

我们可以一个一个把当前线性空间里面的一组基（不是线性基，就是普通的一个基，这个基也能表出线性空间里面的所有数）插入到线性基里面，过程类似于高斯消元。

从高到底枚举当前这个数为 $1$ 的所有位，如果第 $i$ 位当前没有值，那就让当前的值插入到第 $i$ 位，如果第 $i$ 位当前有值，那就要让当前的值异或上第 $i$ 位的值，继续循环。

如果最后还是没有插入线性基，说明这个值是可以被表出来的，那么这个值就没有用了。

构造过程如下：

1
2
3
4
5
6
7
8
9

inline void insert(ll x){
	for(ll i=50;i>=0;i--){
		if((x>>i)&1){
			if(!col[i]){col[i] = x;return ;}
			x ^= col[i];
		}
	}
	has=1;
}

has 是标记是否会有一个非空集合异或起来为 $0$。

性质

所有线性基的大小都相同，显然可得。

并且先后插入线性基的顺序不影响最终线性基的大小，由上一条可得。

第 $i$ 个数值的二进制下的第 $i$ 位一定为 $1$。

线性基里面的所有数线性无关，任意不同集合表出来的数都不相等。

功能

求最大值

我们可以从高位到低位枚举线性基的每一个位上的值，每一次都让 $ans \gets \max(ans,ans \operatorname{xor} p_i)$。

当然，也可以判断 $ans$ 的第 $i$ 位和 $p_i$ 的第 $i$ 位（肯定为 $1$）异或起来是不是 $1$，如果是就异或 $p_i$ 即可。

这样子的结论贪心显然可得，代码如下：

1
2
3
4
5

inline ll query(){
    ll ans = 0;
    for(ll i=len;i>=0;i--) if(((p[i]>>i)&1)^ans[i]) ans=ans^p[i];
    return ans;
}

求最小值

首先判断有没有集合异或起来等于 $0$，即前面的 has 变量是否为 $1$。

然后输出线性基的 $i$ 最小的，$p_i$ 不为 $0$ 的 $p_i$ 即可。

贪心也可证明。

求第 $k$ 小值

我们这个时候需要对线性基做一定的转化。

如果 $p_i$ 有值，我们要让其他 $p_j$ 的第 $i$ 位都为 $0$，这样处理很简单，只需要模拟一下高斯消元的回代即可。

最后记得如果 $p_i$ 被异或成 $0$ 了需要删除掉，假如删除之后有 $l$ 个元素在线性基 $s$ 里面，并且没有异或集合为 $0$（有的话可以让 $k$ 减一），那么把 $k$ 进行二进制拆分，如果 $k$ 的第 $i$ 位为 $1$，那么答案异或上 $s$ 即可。

这个方法的正确性源于线性基的所有数是线性无关的，并且通过贪心的选择可以证明从底往高按照二进制划分是对的。

同时，求最大值就是全部异或起来，求最小值就是最后一个元素，也证明了上面求最小值的方案是正确的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,i,col[51],tmp[51],tot,x,has,ans;
inline void insert(ll x){
	for(ll i=50;i>=0;i--){
		if((x>>i)&1){
			if(!col[i]){col[i] = x;return ;}
			x ^= col[i];
		}
	}
	has=1;
}
inline void init(){
	for(ll i=0;i<=50;i++){
		for(ll j=i-1;j>=0;j--) if((col[i]>>j)&1) col[i]^=col[j];
		if(col[i]!=0) tmp[tot++]=col[i];
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	while(n--) cin>>x,insert(x);
	init();
	cin>>n;
	while(n--){
		cin>>x;
		if(has){
			if(x==1){
				cout<<0<<endl;
				continue;
			}
			else x--;
		} 
		if(x>=(1ll<<tot)){
			cout<<"-1\n";
			continue;
		}
		ans = 0;
		for(i=0;i<tot;i++) if((x>>i)&1) ans^=tmp[i];
		cout<<ans<<endl;
	}
	return 0;
} 

求集合异或为 $0$ 的不同集合个数

包括空集。

我们首先构造线性基，那么设线性基大小为 $k$，集合大小为 $n$，那么我们在剩下 $n-k$ 个数里面随便选择一些数，根据线性基的性质都能在线性基里面找到唯一一个集合异或出来等于这个结果，那么方案数量就是 $2^{n-k}$。

应用

应用主要是前缀线性基，也就是第 $i$ 位不仅记录第 $i$ 位的值，也要记录第 $i$ 位是集合中哪个数插入进来得到的。

例题：

给定 $n$ 和 $a_{1,\dots,n}$，$q$ 次询问，每次询问在 $[l,r]$ 区间内选出若干个数异或和最大是多少。

我们可以从 $1$ 遍历到 $n$，每个下标都记录一下线性基的数据，线性基大小是 $\log$ 级别的，所以空间可以承受。

然后我们可以插入的时候优先保留下标靠后的数，因为越靠后越能产生贡献，并且因为线性基大小不变，所以不会产生不良影响。

于是可持久化一下，外加更新的时候判断当前有数了，但是下标小于插入的数的下标就交换一下即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	ll pos[31],p[31];
	inline void insert(node a,ll x,ll id){
		for(ll i=30;i>=0;i--) pos[i]=a.pos[i],p[i]=a.p[i];
		for(ll i=30;i>=0;i--){
			if((x>>i)&1){
				if(!p[i]){p[i]=x,pos[i]=id;return ;}
				else if(pos[i]<id){swap(pos[i],id),swap(p[i],x);}
				x ^= p[i];
			}
		}
	}
	inline ll query(ll x){
		ll ans = 0;
		for(ll i=30;i>=0;i--) if(pos[i]>=x) ans=max(ans,ans^p[i]);
		return ans;
	}
}a[500005];
ll n,i,x,q,l,r;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>x;
		a[i].insert(a[i-1],x,i);
	}
	cin>>q;
	while(q--){
		cin>>l>>r;
		cout<<a[r].query(l)<<endl;
	}
	return 0;
} 

同时，线性基还可以运用在树上，就是根节点到某个节点路径上的异或信息。

线性基还经常和 bitset 连用，这个时候求最大值就不能取 max 了，必须是判断当前位的值，不然时间会耗费很多。

当然，也有结合线段树分治的做法，也就是一段时间会有一个数加入集合，这个操作方式就跟并查集一样的，只是最后弹出的时候我们可以直接通过前缀线性基的方法（记录下标）判断就可以了。