线性基算法概述

  万万没想到,笔者高中打 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())
▲ 异或线性基的实现,可以输出方案