万万没想到，笔者高中打 oi 时学的线性基算法，从来没在 oi 比赛中用到过，反倒前几天在 TCTF 2020 用上了。所以写一篇博客，讨论线性基这一类算法。
所谓线性空间（也称向量空间），定义如下：
给定域 $F$，$F$ 上的向量空间 $V$ 是一个集合，其上定义了两种二元运算：
- 向量加法 $+ : V\times V \to V$
把 $V$ 中的两个元素 $\boldsymbol{u}$ 和 $\boldsymbol v$ 映射到 $V$ 中另一个元素，记作 $\boldsymbol u + \boldsymbol v$ - 标量乘法 $\cdot : F \times V \to V$
把 $F$ 中的一个元素 $a$ 和 $V$ 中的一个元素 $\boldsymbol u$ 变为 $V$ 中的另一个元素，记作 $a\cdot\boldsymbol u$
$V$ 是向量空间，当且仅当 $\forall a,b\in F, \forall \boldsymbol u, \boldsymbol v, \boldsymbol w \in V$，以下性质全部成立：
- 向量加法结合律：$\boldsymbol u + (\boldsymbol v + \boldsymbol w) = (\boldsymbol u + \boldsymbol v) + \boldsymbol w$
- 向量加法交换律：$\boldsymbol u + \boldsymbol v = \boldsymbol v + \boldsymbol u$
- 向量加法单位元：$\exists \boldsymbol 0 \in V$，使得 $\forall \boldsymbol u \in V, \boldsymbol u+0 = \boldsymbol u$
- 向量加法逆元：$\forall \boldsymbol v \in V, \exists -\boldsymbol v \in V$，使得 $\boldsymbol v + (-\boldsymbol v) = 0$
- 标量乘法与标量域乘法相容： $a(b\boldsymbol v) = (ab)\boldsymbol v$
- 标量乘法单位元：$\exists 1 \in F$，使得 $1\boldsymbol v = \boldsymbol v$
- 标量乘法对向量加法分配律：$a(\boldsymbol u + \boldsymbol v) = a\boldsymbol u + a\boldsymbol v$
- 标量乘法对域加法分配律：$(a+b)\boldsymbol v = a\boldsymbol v + b\boldsymbol v$
可见线性空间的定义是很苛刻的。但越苛刻的定义，会带来越优秀的性质。我们最常见的线性空间是欧几里得空间 $\mathbb{R}^n$，也就是线性代数课程讨论的。
欧几里得空间中的基
在讨论线性空间的基之前，我们有必要明确“线性组合”的概念。一个原始的例子，我们在高中时就接触过：“平面上两个不共线向量可以表示任意一个向量”，也就是说，在平面 $\mathbb{R^2}$ 上，若有两个不共线向量 $\boldsymbol u,\boldsymbol v$，则平面上的任意向量可以表示为：$$\lambda \boldsymbol u + \mu \boldsymbol v$$
我们把这个概念扩展到所有线性空间上。说一个向量 $\boldsymbol t$ 能被一组向量 $ \boldsymbol {a}_1, \boldsymbol a_2,\cdots,\boldsymbol a_n$ 线性表示，当且仅当存在 $\lambda_1, \lambda_2 ,\cdots \lambda_n \in \mathbb{R}$，使得$$t = \lambda_1 \boldsymbol a_1 + \lambda_2 \boldsymbol a_2 + \cdots + \lambda_n \boldsymbol a_n$$
举一个例子。考虑 $\mathbb{R}^3$ 上的一组向量 $(0,0,1), (0,1,0)$，它们可以线性表示出 $z=0$ 平面上的每一个点，但无法表示这个平面以外的任何一个点。而只要把 $(1,2,3)$ 加入这组向量，它就能线性表示出 $\mathbb{R}^3$ 上的每一个点。
我们把一组向量所能线性表示的所有的向量的集合，称为这组向量的“张成空间”。利用线性代数中的结论我们知道，任意一个线性空间，都可以描述为其中一组向量的张成空间。
我们把最小（向量个数最少）的足以张成整个线性空间的向量组，称为这个线性空间的基。基往往有无数个，例如对于 $\mathbb{R}^2$ ，任意两个不共线、不为零的向量，都可以组成基。
我们接下来想解决这一个问题：给定一个基，如何判断指定的向量是否在这个基的张成空间上？也就是说，指定向量能否被我们的基线性表示？先在欧几里得空间上考虑这个问题。
Gram-Schmidt 正交化算法
正交基是指“向量两两正交”的基。
为什么我们执着于正交基？假设手上有 $(x_1, y_1, z_1), (x_2, y_2, z_2)$ 这个基，想判断 $(x_3, y_3, z_3)$ 是否能被基线性表示，我们得去解方程：$$\begin{cases}\lambda x_1 + \mu x_2 = x_3 \\ \lambda y_1 + \mu y_2 = y_3 \\ \lambda z_1 + \mu z_2 = z_3 \end{cases}$$
如果有合适的 $\lambda, \mu$ 让上面三个方程都成立，则可以线性表示，否则不行。然而解方程是很复杂的工作，对于一个秩为 $n$ 的基，如果采用高斯消元，会付出 $O(n^3)$ 的代价，这是难以接受的。
但如果我们的基是正交的，那么我们可以求出向量在各个基向量方向上的分量。通过点积，这是可以做到的！求出各分量之后，用这些分量去组合基向量，如果恰好得到目标向量，则可以表示；否则不可以线性表示。这个复杂度是 $O(k\cdot n)$ 的，其中 $n$ 是欧几里得空间维数，$k$ 是基的个数。
因此，只要能把欧几里得空间中的向量组变成正交基，那么接下来的判断工作就迎刃而解了。Gram-Schmidt 正交化算法就是解决这个问题的。
由于线性代数教程都会描述这一算法，我们不再赘述。维基百科：格拉姆-施密特正交化
异或空间的线性基
我们来考虑这样一个算法问题。初始集合为空，下面的“数”都是 unsigned int 类型。要高效支持下面的操作：
- 把一个数加入集合
- 询问一个数能否通过集合中的若干个数的异或和表示
这就是算法竞赛中的线性基。首先我们注意到，一个 32 位无符号整数，等价于一个 32 位向量，其中每一位要么取 0，要么取 1. 向量的加法定义为异或，标量乘法 $a\cdot \boldsymbol v$ 定义为 $\boldsymbol v$ 与自己异或 $a$ 次。那么不难发现，32 位整数空间 $V$ 是一个线性空间。
现在我们想找到一种“判断某个数能否由已有的数异或而成”的算法。如果真的用原始的那个向量组去凑，复杂度是枚举子集的复杂度，也就是 $O(2 ^ n)$，其中 $n$ 是向量个数。因此肯定是不行的，我们需要像欧几里得空间那样，把基变成容易用来凑数的基。
欧几里得空间里面有“正交”概念，但异或这里没有。我们找了另一条路：逐位拼凑。如果我们的基向量的第一个 1 的位置互不相同，那么我们一眼就可以看出目标向量能否用这些基向量凑出来 —— 目标向量哪一位是 1 ，就拿对应首位是 1 的基向量异或起来；如果没有那一位是 1 的基向量，那么就失败了，说明目标向量不在这个基的张成空间里面。如果做到最后，目标向量被我们异或成 0 了，那就说明目标向量可以由这个基线性表示。
往基里面添加向量也很简单：先走一遍上面的流程，如果最后结果不在基里面，则把它加入基。最终代码如下：
import numpy as np
import random
from ys import ys # 一些数
def itoline(n):
res = []
for x in range(64):
res.append((n>>x) & 1)
return np.array(res[::-1])
def xorLine(a, b):
c = np.zeros(64, dtype=int)
for x in range(64):
c[x] = a[x] ^ b[x]
return c
def norm(lis):
s = set(lis)
res = []
for x in s:
if lis.count(x) % 2 == 1:
res.append(x)
return res
def getXor(lis):
res = 0
for x in lis:
res ^= ys[x]
return res
class Basis():
def __init__(self):
self.m = np.zeros([64, 64], dtype=int)
self.ori = [list() for x in range(64)]
def debug(self):
print(self.m)
def add(self, n, nid):
v = itoline(n)
p = [nid]
for i in range(64):
if v[i] == 1:
if self.m[i, i] == 1:
v = xorLine(v, self.m[i, :])
for x in self.ori[i]:
p.append(x)
else:
p = norm(p)
self.m[i] = v
self.ori[i] = p
print(p)
return
def has(self, n):
v = itoline(n)
p = []
for i in range(64):
if v[i] == 1:
if self.m[i, i] == 1:
v = xorLine(v, self.m[i, :])
for x in self.ori[i]:
p.append(x)
else:
return False
p = norm(p)
print(f'The basis has {n}')
print(p)
print(getXor(p))
return True
def rank(self):
res = 0
for i in range(64):
if self.m[i, i] != 0:
res += 1
return res
b = Basis()
for t, y in enumerate(ys):
b.add(y, t)
print(b.rank())