线性基是常用来解决子集异或/线性空间中一些题目的算法

算法

具体定义概念见Menci的博客，写的很好，这里只记录一些感性的理解

注：以下没有注明的话，线性基均指的是异或线性基

简介

简单来说，线性基就是在异或运算下，只需要一个大小为cc的集合β\beta（cc表示数字位数）就能通过相互进行异或运算表示出一个全集SS中的所有数。也就是说，它可以将集合SS在异或意义下的一个压缩

为什么只需要大小为cc的集合呢？显然，只需要一个全是2的幂次的集合就能表示出所有数，因此上界肯定是cc

它可以表示成这样一组数（也可以说是一组0/10/1向量）： ，其中axa_x的最高位的11在第xx位

而在这里所提到的线性基（包括代码实现）都是最简意义下的。即只要某一位它出现在了某个数的最高位，那么其他数字中它这一位就为00（如果不为00就可以消掉）；而如果某一位没有作为最高位出现过，可以有多个数字这一位为00

由此不难看出，它是一个类似于对角矩阵的东西，大概可能长这样：

[1010⋯0000110⋯0100000⋯0000001⋯0000000⋯1100000⋯0000000⋯001] \begin{bmatrix} 1&0&1&0&\cdots&0&0&0\\ 0&1&1&0&\cdots&0&1&0\\ 0&0&0&0&\cdots&0&0&0\\ 0&0&0&1&\cdots&0&0&0\\ 0&0&0&0&\cdots&1&1&0\\ 0&0&0&0&\cdots&0&0&0\\ 0&0&0&0&\cdots&0&0&1 \end{bmatrix}

其中第ii行表示线性基中的aia_i

实现

显然，我们可以用O(nc2)O(nc^2)的高斯消元暴力求线性基，但是这样并不优美。于是有一种O(nc)O(nc)贪心动态构造的方法：

对于一个新加入的数xx，从大到小枚举xx的每一个为11的二进制位ii：

  • 如果ai=0a_i=0，那么令ai=xa_i = x

    用已经存在的aj(j<i)a_{j(j<i)}消掉xx在第jj位的影响

    用当前的xx消掉已经存在的aj(j>i)a_{j(j>i)}在第ii位的影响

    并结束插入的过程

  • 否则x=x⊕aix = x \oplus a_i

这样贪心的构造显然是对的，证明见文章开头的博客，这里不多赘述

写一下感性理解，对于当前为11的最高位ii，如果ai≠0a_i\ne0，就说明已经存在一个最高位为ii的数，那么直接用这个aia_i就能把xx的第ii位消掉；而如果ai=0a_i=0，就说明此时的xx是最先出现的最高位为ii的数，直接插进线性基即可

合并

扫一遍线性基，暴力插入另一个即可

复杂度O(c2)O(c^2)

具体见此

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
namespace Basis
{
	const int Maxlen = 30;

	int A[Maxlen + 10];

	inline int insert (int x)
	{
		for (int i = Maxlen; ~i; --i)
		{
			if (!(x & (1 << i))) continue;
			if (!A[i])
			{
				for (int j = 0; j < i; ++j) if (x & (1 << j)) x ^= A[j];
				for (int j = i + 1; j <= Maxlen; ++j) if (A[j] & (1 << i)) A[j] ^= x;
				A[i] = x;
				return 1;
			}
			x ^= A[i];
		}
		return 0;
	}
}

应用

求异或最大/小值；与xx异或的最大/小值

高位往低位贪心，如果异或上当前的数能使答案更优就异或

求异或kk小值

由于线性基中从高位往低位的前缀异或和显然是单调不降的，因此只需要对kk做二进制拆分，取线性基中对应位数的值异或起来即可

核心代码：

1
2
for (int i = 0; i <= Maxlen; ++i) if (A[i]) v.push_back(A[i]);
for (int i = 0; i < v.size(); ++i) if (k & (1ll << i)) ans ^= v[i];

求异或排名

与上个操作是互逆操作

核心代码：

1
2
for (int i = 0; i <= Maxlen; ++i) if (A[i]) bit.push_back(i);
for (int i = 0; i < bit.size(); ++i) if (x & (1ll << bit[i])) ans |= (1 << i);

解异或方程组

见「SDOI2010」外星千足虫

扩展到线性空间

线性基也可以用来求解线性空间的解方程/线性无关问题

具体可见「JLOI2015」装备购买 ，但是我并没有写博客，就把代码放这里：

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
namespace Basis
{
	long double A[Maxn][Maxn];
	int Vis[Maxn];

	inline int insert (long double x[])
	{
		for (int i = 1; i <= N; ++i)
		{
			if (fabs(x[i]) < eps) continue;

			if (!Vis[i])
			{
				long double base = x[i];
				for (int j = i; j <= N; ++j) x[j] /= base;

				for (int j = i + 1; j <= N; ++j)
				{
					if (!Vis[j]) continue;
					base = x[j];
					for (int k = 1; k <= N; ++k) x[k] -= base * A[j][k];
				}

				for (int j = 1; j < i; ++j)
				{
					if (!Vis[j]) continue;
					base = A[j][i];
					for (int k = 1; k <= N; ++k) A[j][k] -= base * x[k];
				}

				for (int j = 1; j <= N; ++j) A[i][j] = x[j];
				Vis[i] = 1;
				return 1;
			}

			long double base = x[i];
			for (int j = i; j <= N; ++j) x[j] -= base * A[i][j];
		}
		return 0;
	}
}

最大路径异或和

见「WC2011」Xor - 线性基

树上路径最大异或和

见「WC2011」Xor

其他应用基本都是建立在这些操作之上了