线性基 — 异或和处理利器

给出几个数，让您从中任选几个数使得它们的异或和最大，或者求出第 K 小异或和。这就需要线性基来处理。

引入

线性基就是一个容器。我们设这个容器为 $P$，则 $P_i$ 记录二进制最高位 $1$ 在第 $i$ 位的数。显然，线性基大小应该是 $\log_2N_{max}$ 的（因为需要记录二进制的每一位）。

基本操作

插入

让我们给出一组数，从前往后扫。对于每一个数，我们找出它二进制最高位 $1$ 所在的位置（暴力从最高位枚举即可），如果该位置对应的线性基为空，就插入这个数；如果不为空，则把这个数异或线性基上的数（$x = x \oplus P_i$）继续找，直到找到能够插入的位置为止。

$x$ 最终会被插入到线性基中，或者没有插入最终变成 $0$ 。

举个栗子
给出这列数。

23 9 10 12 5

它们的二进制形式和二进制最高位 1 所在二进制位分别是

23:10111    4
9:1001      3
2:10        1
12:1100     3
5:101       2

那让我们把它们插入线性基。

23 -> p[4]
9 -> p[3]
2 -> p[1]
12 ^ 9 = 5 -> p[2]
5 ^ 5 = 0 不插入线性基

最终得到的线性基 $P_4\dots P_0$ 分别为 $23,9,5,2,0$。 其二进制形式长这样 （是不是非常整齐呢）

4:10111
3:-1001
2:--101
1:---10
0:-----

代码
maxL 指的是最高的二进制位。如 long long 类型是 64 位整型，则最高位是第 62 位（0~63位，其中有一个是符号位），所以从第 62 位开始枚举即可。

void ins(long long x) {
	for (int i = maxL; i >= 0; i--)
		if (x & (1LL << i)) {
			if (!p[i]) {
				p[i] = x;
				return;
			}
			x ^= p[i];
		}
}

合并线性基

暴力插入即可。（如果为空则插入，如果不为空就跳过）

线性基查询

查询最大异或和

我们从线性基的最高位开始枚举。显然越高位为 1 则异或和最大，所以可以采用一种贪心策略。

for (int i = maxL; i >= 0; i--)
	ans = max(ans, ans ^ p[i]);

看到这里你就可以做出这道模板题了。

查询最小异或和

从线性基最低位枚举即可。线性基最低位上的数即为结果。

查询某个数是否可以异或得到

从高位到低位扫描。类似于插入操作只不过不进行插入。

如果第 $i$ 位为 1，且该位对应的线性基不为空，则异或线性基上的数（$x = x \oplus P_i$）继续扫描。 如果最后这个数变成了 0，则说明可以。

查询第 K 小异或和

再来一个数组来进行操作，将原来的线性基进行重新构造。

依然是从高位到低位枚举。若 $j < i$，当第 $i$ 位线性基存在且该线性基上的数第 $j$ 位为 1 时，就把 $P_i$ 异或上 $P_j$（$P_i = P_i\oplus P_j$）。

这样处理之后线性基每一位都相互独立了，大概长这样

还是这列数 23 9 10 12 5
4:10001    17
3:-1001     9
2:--101     5
1:---11     3
0:-----     0

最后从低位到高位扫描一下进行上述处理后的线性基，如果该位的线性基存在，则加入到新的数组中。

最后求第 K 大时只需要从高位到低位枚举，如果 K 的第 $i$ 位为 1，则让 $ans$ 异或新数组的第 $i$ 位。（$ans$ 初始值为 $0$）。

代码

long long query_kth(int k) {
	long long tmp[maxL + 3], ans = 0, cnt = 0;
	for (int i = maxL; i >= 0; i--)
		for (int j = i - 1; j >= 0; j--)
			if (p[i] & (1LL << j)) p[i] ^= p[j];
	for (int i = 0; i <= maxL; i++)
		if (p[i]) tmp[cnt++] = p[i];
	if (k >= (1LL << cnt)) return -1;
	for (int i = maxL; i >= 0; i--)
		if (k & (1LL << i)) ans ^= tmp[i];
	return ans;
}