概述

线性基是一类用于方便解决数字的异或问题的方法，可以实现O(n \log(max))维护基集合、O(n)进行其他一些查询操作的复杂度。下面是对线性基及其相关知识的介绍。

线性代数前置知识

向量空间（Vector space）

定义

给定域F，F上的向量空间V是一个集合，其上定义了两种二元运算：

• 向量加法 + : V × V → V，把V中的两个元素 u 和 v 映射到V中另一个元素，记作 u + v；
• 标量乘法 · : F × V → V，把F中的一个元素 a 和 V 中的一个元素 u 变为V中的另一个元素，记作 a · u。

V中的元素称为向量，相对地，F中的元素称为标量。
而集合V公理才构成一个向量空间（对F中的任意元素a、b以及V中的任意元素u、v、w都成立）：

前四个公理说明装备了向量加法的V是交换群，余下的四个公理应用于标量乘法。需要注意的是向量之间的加法“+”和标量之间的加法“+”是不一样的，标量与向量之间的标量乘法·和两个标量之间的乘法（域F中自带的乘法）也是不一样的。
简而言之，向量空间是一个F−模。

性质

以下是一些可以从向量空间的公理直接推出的性质：

• 零向量0是唯一的；
• 对任意a ∈ F，a · 0 = 0；
• 对任意u ∈ V，0 · u = 0（0是F的加法单位元）。
• 如果a · u = 0，则要么a = 0，要么u = 0。
• 向量加法的逆向量v是唯一的，记作−v。u + (−v)也可以写成u − v，两者都是标准的。
• 对任意u ∈ V，−1 · u = −u.
• 对任意a ∈ F以及u ∈ V， (−a) · u = −(a · u) = a · (−u).

线性组合（Linear combination）

即形如w = a_1v_1 + a_2v_2 + a_3v_3 + \dots + a_nv_n的w，其中所有a为标量，而v可以为任意类型的项，如向量或标量。

线性无关（Linear independence）

向量空间的一组元素中，若没有向量可用有限个其他向量的线性组合所表示，则称为线性无关，反之称为线性相关。

基（Basis）

定义

给定一个向量空间V，V的一组基\mathfrak{B}是指V里面的可线性生成的V的一个线性无关子集。
设\mathfrak{B} = \{ \mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n \}是在系数域\mathbb{F}上的向量空间V的有限子集。如果\mathfrak{B}满足以下条件：

1. 对任意 (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{F}^n ，如果 \lambda_1\mathbf{e}_1 + \lambda_2\mathbf{e}_2 + \dots + \lambda_n\mathbf{e}_n = 0 ，则必然 \displaystyle \sum_{i=1}^n \lambda_i = 0 ；
2. 对任意v \in \mathrm{V}，可以选择 (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{F}^n ，使得 v = \lambda_1\mathbf{e}_1 + \lambda_2\mathbf{e}_2 + \dots + \lambda_n\mathbf{e}_n 。

就说\mathfrak{B}是向量空间V的一组基。

性质

设\mathfrak{B}是向量空间V的子集。则\mathfrak{B}是基，当且仅当满足了下列任一条件：

1. V是\mathfrak{B}的极小生成集，就是说只有\mathfrak{B}能生成V，而它的任何真子集都不能生成全部的向量空间。
2. \mathfrak{B}是V中线性无关向量的集大集合，就是说\mathfrak{B}在V中是线性无关集合，而且V中没有其他线性无关集合包含它作为真子集。
3. V中所有向量都可以按唯一的方式表达为\mathfrak{B}中向量的线性组合。如果基是有序的，则在这个线性组合中的系数提供了这个向量关于这个基的坐标。

“线性基”算法

异或意义下的向量空间与基

如果我们定义一个向量空间V，其中F = \{0, 1\}，给定一个集合\mathfrak{B}作为基，此时向量实际上是一个01组成的向量，可以看做一个整数的二进制表示，将加法定义为这些对应的整数的异或，数乘不变。我们来研究这样的向量空间的性质。
首先异或运算是满足上述公理的，这个向量空间的V显然是这些基能异或表示出的所有整数。这样，如果我们有一个集合，想求这个集合内的数字异或能表示哪些数字，实际上只需要把这个基\mathfrak{B}求出来就可以了，利用向量空间的性质，我们可以处理一些对异或的询问。

维护基集合

我们考虑使用类似高斯消元的方法，维护一个右上三角矩阵，对于集合中的每个数，插入该三角阵时，首先枚举二进制的每一位，若遇到该位为1且三角阵该行对角线上也为1，则应该用三角阵该行异或该数，反之令三角阵该行为该数（的二进制表示向量）。
C++代码实现如下（默认数据为64位有符号整数）：

for(int i = 1; i <= n; i++) {
    for(int j = 63; j >= 0; j--) {
        if(a[i] & (1ll << j)) {
            if(mat[j]) {
                a[i] ^= mat[j];
            } else {
                mat[j] = a[i];
                break;
            }
        }
    }
}

各种查询操作的实现

是否能异或出某个数

类似插入的思路，用三角阵检验每一位异或掉后是否能将该数消至0。

能表示出的异或最大值

从高位向低位枚举每一位，如果异或上该位的基会使答案更大，则将其异或进答案中。

能表示出的异或最小值

最低位上的基。

能表示出的异或k小值

考虑k的二进制表示，对于为1的位，异或上该位的基即可。

例题：[BJWC2011]元素

参考资料

• 向量空间 – 维基百科，自由的百科全书
• 线性组合 – 维基百科，自由的百科全书
• 线性无关 – 维基百科，自由的百科全书
• 基 (线性代数) – 维基百科，自由的百科全书
• [学习笔记]线性基 – CSDN博客
• 线性基学习笔记 | Sengxian’s Blog