线性基

定义

张成

一个集合 $s$ 的所有非空子集的异或和所组成的集合为 $s$ 的张成，记作 $\operatorname{span}(s)$。

线性相关 & 线性无关

如果一个集合 $s$ 存在一个元素 $x$ 使得 $s$ 去掉 $x$ 之后形成的集合 $s'$ 满足 $x \in \operatorname{span}(s')$，则称 $s$ 线性相关。

其实就是 $s$ 存在一个元素可以由其它几个元素异或得到，而且从这可以知道，去掉一个线性相关的集合 $s$ 里像 $x$ 一样的元素后，$s$ 的张成不变。

反之，则称集合 $s$ 线性无关。

线性基

我们称 $t$ 是 $s$ 的线性基，当且仅当：

• $s \subseteq \operatorname{span}(t)$；
• $t$ 线性无关。

性质

$s$ 的线性基 $t$ 有两个基本性质：

• $t$ 不存在一个真子集 $u$ 使得 $u$ 是 $s$ 的线性基。

  因为 $t$ 线性无关，所以无法去掉 $t$ 的任意元素使得 $t$ 的张成不变。

• $s$ 的每个元素都可以被唯一表示为 $t$ 的若干元素的异或和。

  首先因为 $s \subseteq \operatorname{span}(t)$，所以 $s$ 的每个元素都可以被表示为 $t$ 的若干元素的异或和。

  接下来使用反证法证明这个表示是唯一的。

  假设 $s$ 中一个元素 $x$ 等于 $t$ 的子集 $u$ 的异或和，也等于子集 $v$ 的异或和，且 $u$ 和 $v$ 没有交集。（$u$ 和 $v$ 的公共部分是没有意义的）

  然后 $u$ 中的一个元素 $y$ 可以被自己异或得到，也可以被 $u$ 里的剩余元素和 $v$ 的所有元素异或而成，这不满足 $t$ 的线性无关性。

构造

我们使用一个数组 $b$ 存储线性基，当 $b_i \ne 0$ 时我们称第 $i$ 位存在。

这样构造出来的线性基有一个有用的限制：每个元素最高位互不相同。

我们考虑将数一个一个插入线性基。

根据线性基的性质，$n$ 个元素中，只要有一个元素第 $i$ 位为 $1$，第 $i$ 位就存在。所以如果数据随机，线性基的大小就比较大，这个性质有时候会应用。

插入过程

设插入的数为 $x$，考虑从高位考虑到低位，假设现在考虑到第 $i$ 位。

• 如果 $x$ 的第 $i$ 位为 $0$，直接进入下一位的考虑即可。
• 否则：
  • 如果第 $i$ 位存在，我们需要将 $x$ 的第 $i$ 位消除，（因为只有 $b_i$ 的第 $i$ 位为 $1$）把 $x$ 异或上 $b_i$ 即可。
  • 如果第 $i$ 位不存在，我们将 $x$ 插入 $b$。

如果 $x$ 自始至终都没有被插入，那就说明 $x$ 可以被线性基里的一些数异或出来，如果插入就不满足线性无关性。

证明

因为我们对 $x$ 以及 $b$ 的操作都是互相异或，这些操作显然是可逆的，所以用 $b$ 的一些元素的异或和可以表示出原本的 $x$。

代码

void insert(ll x){
	for (int i = 49;i >= 0;i --){
		if (x >> i & 1 ^ 1) continue;
		if (b[i]) x ^= b[i]; // 用 b[i] 消去 x 的第 i 位
		else { // 可以插入
			b[i] = x; // 插入
			break; // 一定不要忘记
		}
	}
    // 如果没被插入（即 x 被异或成 0）就说明不需要 x
}

应用

子集最大异或和

令答案为 $ans$，初始为 $0$，然后我们考虑倒序枚举位 $i$，如果 $ans \oplus b_i > ans$，就令 $ans$ 等于 $ans \oplus b_i$，因为根据特殊性质，以后就没有改变 $ans$ 的第 $i$ 位的机会。

子集最小异或和

根据根据特殊性质，答案为 $b_i$ 的最小值。

子集 $k$ 小异或和

如果数全都被插进线性基，选出线性基的一个非空子集有 $2^{|s|} - 1$ 种方案。

否则，有异或和为 $0$ 的情况，一共有 $2^{|s|}$ 种方案，如果 $k$ 为 $1$，输出 $0$ 即可，否则令 $k$ 减 $1$（去掉异或和为 $0$ 的情况）。

令答案为 $ans$，初始为 $0$，然后我们考虑 $k$ 的每一个二进制位，假设考虑到第 $i$ 位：

• 令 $x = \min(ans, ans \oplus b_i), y = \max(ans, ans \oplus b_i)$。

• 如果该位为 $1$，那么令 $ans$ 为 $y$。

• 否则令 $ans$ 为 $x$。