浅谈线性基

线性基可以用来解决一些有关子集异或和的问题。

定义

对于一个数组，他的线性基（是一个数组）满足以下条件。

• 对于原数组所有子集（不能为空）的异或和，都可以用线性基的一个子集（不能为空）表示出来。
• 所包含的元素最小。

我们知道了线性基的定义，我们来看看如何求出来线性基。

性质

线性基有一个性质，就是线性基里的数可以互相异或，异或后还是原数组的线性基。

假设我们将 $p_i$ 异或上 $p_j$ ，如果以后要用到原本的 $p_i$ ，我们就异或上 $p_i\oplus p_j$ 。如果我们需要用上 $p_i\oplus p_j$ ，那就异或上 $p_i$ ，这就不会影响到线性基所能表示的异或和。

求法

我们把原数组从头到尾遍历，如果一个数他不能被当前的线性基表示出来，我们就将他加到线性基里。

我们来看看如何加到线性基里。

我们设 $p_i$ 表示在二进制下最高的为 $1$ 的位是第 $i$ 位的一个数。

如果我们当前枚举的数的最高位是 $j$ ，如果 $p_j$ 有值，说明我这一位可以被异或出来，那我就将这个数异或上这个值，然后继续找当前数的最高位。

如果 $p_j$ 没有值，则说明这个数的第 $j$ 位不能被异或出来，我们就将 $p_j$ 设为当前的值。

为什么不设为 $2^j$ 呢？

因为我们可以看成在当前来说，二进制下这几个 $1$ 一起出现会使得线性基尽量小。

upd : 当时估计想错了，其实是因为你需要保证元素最少，同时所有都要能被表示，如果设为 $2^j$，那就需要更多的位数来表示这个数。

如果后面需要把二进制下这几个 $1$ 分开，我们就把分开的 $1$ 再用一个值表示就好了。（由于线性基的性质，我们可以看作分成的两个值中一个异或上了另一个）

这样子，我们的线性基就能被求出来了。

for (int i = 1; i <= n; i++)// 遍历每个数
		for (int j = 63; j >= 0; j--)// j的起点为你可能出现的最高位
			if (a[i] >> j) {// 如果当前位为1
				if (p[j] == 0) { 
					p[j] = a[i];
					break; 
				}
				else
					a[i] = a[i] ^ p[j];
			}
1
2
3
4
5
6
7
8
9
10