数学 - 线性基

定义

将 $64$ 位二进制数看成长度 $64$ 的 $0/1$ 向量，那么异或就是在模 $2$ 意义下的向量加法。

我们可以把给定的 $m$ 个非零（下文解释）的数 $\{x_1,x_2,\dots,x_m\}$ 取出一组异或线性基 $B=\{b_1,b_2,\dots,b_r\}$，满足：

1. 任何 $x_i$ 都可以被若干个 $b_j$ 的线性组合表示；
2. 任何 $b_i$ 都不可以被若干个 $b_j(j\neq i)$ 的线性组合表示（线性无关）。

由于在模 $2$ 意义下数字只有 $0/1$，所以这里的线性组合就表示 $k_1b_1\oplus k_2b_2\oplus \cdots\oplus k_rb_r$，其中 $k_i\in\{0,1\}$。

事实上，这就是线性代数中极大无关组的概念。对上面两条概念形式化地表示，就是：

1. 对任意的 $x_i$，存在一组 $\{k_j\}$ 使得 $x_i=\bigoplus_{j=1}^r k_jb_j$。
2. 对任意的 $b_i$，若 $b_i=\bigoplus_{j=1}^r k_jb_j$，必有 $k_j=\begin{cases}1\quad j=i\\0\quad j\neq i\end{cases}$。

对第二条性质，我们可以做出推论：对 $B$ 的任意非空子集，它们的异或和不可能为 $0$。

证明考虑反证法，如果存在一组 $\{k_j\}$ 使得 $\bigoplus_{j=1}^r k_jb_j=0$ 并且 $k_j$ 不全为 $0$，那么通过异或类似移项的操作，不妨设 $k_1=1$，就会有 $b_1$ 可以被若干个 $b_j(j\neq 1)$ 线性表示，与定义矛盾。

如果某个 $x_i=0$，我们可以认为空集的异或和为 $0$，所以不管它。

构造方法

我们首先要证明，对异或线性基进行线性组合，这个线性基仍然线性无关。

反证法，假设 $b_1\oplus \left(\bigoplus_{j=2}^r k_jb_j\right)$ 可以被 $b_j(j\neq 1)$ 线性表示，那么 $b_1$ 就通过移项被线性表示，与定义矛盾。

因此我们总可以让最大的那个 $b_i$，假设它的最高位为 $j$，它通过和别的向量线性组合的方式，让第 $j$ 位为 $1$ 的向量有且只有 $b_i$ 一个。

这就导出了我们的贪心构造方法，初始状态下，最高位 $i=0,1,\dots,63$ 为 $1$ 的向量 $v_i$ 均不存在。

插入一个向量 $x$ 时，贪心地从高位往低位遍历。假设当前遍历到第 $i$ 位，若 $x_i=0$，跳过；若 $x_i=1$，且 $v_i$ 不存在，那么令 $v_i=x$；否则，令 $x\gets x\oplus v_i$ 消掉 $x$ 的第 $i$ 位。

如果循环结束仍然未被插入，说明 $x$ 已经可以被当前的线性基表示出来，因为存在若干个数使得 $x$ 异或它们为 $0$，移项即可得到 $x$ 可以被若干个 $v_i$ 表示。