线性基算法概述

　　万万没想到，笔者高中打 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())