线性空间和OI中的线性基

下面的所有知识均属线性代数范畴。

基础知识

• 线性空间

指关于向量加法和标量乘法两个运算封闭的向量集。

• 表出

如果若干向量 $a_1,a_2,\cdots ,a_k$，能够通过向量加法和标量乘法生成向量 $b$，即 $v_1{a}_1+v_2{a}_2+\cdots v_k{a}_k=b$（$v$ 为标量），则称向量 $b$ 能够被向量 $a_1,a_2,\cdots ,a_k$ 表出，$b$ 也称为向量 $a_1,a_2,\cdots ,a_k$ 的线性组合。

如果向量 $a_1,a_2,\cdots ,a_k$ 所有的线性组合构成一个线性空间，那么 $a_1,a_2,\cdots ,a_k$ 被称为其生成子集。

从空间上看，线性组合是向量 $a_1,a_2,\cdots ,a_k$ 通过伸缩变换和首尾相接组成的一个新向量 $b$。

• 张成

线性空间内所有元素的所有线性组合构成的集合称为该线性空间的张成。

空间上看，所有的向量经过任意的伸缩变换可以组成若干个新的向量，它们将构成这些向量的张成。

注意一点：张成空间的维度一定小于等于所有向量组成空间的维度。

• 线性相关

任选线性空间中的若干个向量，如果其中存在一个向量能够被其它向量表出，则称这些向量线性相关，否则线性无关。

空间上看，如果每次加入一个向量，都会使得整个空间扩展一维，那么这些向量线性无关，否则线性相关。

一个很显然的结论：如果线性空间 $V$ 存在子集 $V^{\prime }$ 线性相关，那么 $V$ 线性相关；如果线性空间 $V$ 的所有子集 $V^{\prime }$ 线性无关，那么 $V$ 也线性无关。

• 基

对于线性空间 $V$，若存在一个线性无关子集 $S$，能够张成 $V$，称 $S$ 为 $V$ 的基，一般写作 $\mathfrak{B}$。我们一般只讨论其大小有限的情况，此时其大小被称为线性空间 $V$ 的维数（从空间角度看，维数实际上就是指基 $S$ 形成的空间维数）。

基存在下列性质：

1. $V$ 是 $\mathfrak{B}$ 的极小生成子集，只有 $\mathfrak{B}$ 能张成 $V$，而它的任何真子集都不张成全部的向量空间 $V$。
2. $\mathfrak{B}$ 是 $V$ 中线性无关向量的极大集合，$\mathfrak{B}$ 在 $V$ 中是线性无关集，同时 $V$ 中没有其他线性无关集合包含它作为真子集。
3. $V$ 中所有的向量都可以按唯一的方式表达为 $\mathfrak{B}$ 中向量的线性组合。

第三点尤其重要。简单来说，基 $\mathfrak{B}$ 就是向量空间中的一个子集，它可以通过唯一的线性组合，来张成向量空间中所有的向量，这样就可以大大的缩小我们向量空间的大小。

如果实在不能理解以上内容，也没有关系，只要您能够看懂下文所引出的概念 “异或空间”，就能够轻松掌握线性基。上文的所有知识只是为您提供一些更为严谨的定义和证明。

线性基

这里重点指 $OI$ 中的线性基。

$OI$ 中的线性基是用于处理集合间相互异或的关系的。

它支持如下操作：

• 插入一个数 $val$；

• 查询某个数 $val$ 是否能够被若干个数异或得出；

• 查询若干个数异或和的 $\max /\min$；

• 查询若干个数异或和的第 $k$ 小；

• $\cdots \cdots$

这里先给出一种好想好写却不太严谨但又能够胜任大多数题目要求的构造方式，单次操作的时间复杂度是 $O({\log }_{2}k)$ 的。

先看插入：

inline void Insert(LL val)
{
    if(val == 0LL) return Zero = true, void();
    for(register int i = MAXLOG - 1; i >= 0; i--)
    {
        if(val >> i & 1LL)
        {
            if(!Base[i]) { Base[i] = val; break; }
            val ^= Base[i];
		}
    }
    return;
}

可以发现这个构造方法非常巧妙，我们来逐行解析一下。

首先我们要知道线性基是处理不了 $0$ 的情况的，因此对于插入的 $0$ 必须特判。事实上，后面的大多数操作都需要这个特判。

然后我们发现，如果在第 $i$ 位没有成功插入，要么这一位不存在，要么就是这一位异或上 $Bas{e}_i$ 变成了 $0$，说明这一位上的数可以被原有的数异或出来，那么它就没有在这一位上插入的必要了；如果这个数在第 $i$ 位成功插入，那么 $Bas{e}_i$ 和更高位上的数也可以把这个数异或出来。这说明，原序列中的每一个数都可以被线性基中的数异或出来。

所以，如果第 $i$ 位上插入没有成功，我们就异或上 $Bas{e}_i$，表示更低位的数与这一位上的数异或起来可以得到我们原来要插入的数。正因为如此，我们还可以发现这个数到了第 $i$ 位时，该数第 $i$ 位的更高位全为 $0$，所以代码中的 if(val >> i & 1LL)也可以写成 if(val >> i)，它们是等价的。

接下来我们看第二个操作：

inline bool Check(LL val)
{
    if(val == 0LL) return Zero;
    for(register int i = MAXLOG - 1; i >= 0; i--) if(val >> i & 1LL) val ^= Base[i];
    return val == 0LL;
}

其实思想也很简单。首先特判 $0$ 是必不可少的。接下来我们从高到低扫描每一位，把对应的每一位上的数异或到一起。前面证明了，原序列中的每一个数都可以被线性基中的数异或出来。所以，用这种方法扫描下去，只要 $val$ 最后等于 $0$（即已经被线性基中的数异或出来了），说明 $val$ 是合法的。反之，如果这种方法无法使得 $val$ 最后等于 $0$，说明 $val$ 不能被线性基中的数异或出来，它是不合法的。

然后是求异或和 $\max$，其实也很简单，就是从大到小扫描，贪心地把每一位填满即可：

inline LL Max()
{
    LL res = 0LL;
    for(register int i = MAXLOG - 1; i >= 0; i--) if((res ^ Base[i]) > res) res ^= Base[i];
    return res;
}

异或和 $\min$ 也很简单，从小到大扫描，第一个扫到的数即为答案，注意特判 $0$ 的情况：

inline LL Min()
{
    if(Zero) return 0LL;
    for(register int i = 0; i < MAXLOG; i++) if(Base[i]) return Base[i];
}

求异或和的第 $k$ 小稍微麻烦一点，因为我们会发现这样构建出的线性基是不满足一个类似二分的性质的。

所以我们要用到一种更加严谨的构造方法：高斯消元。

不过需要提到一点：高斯消元的单次时间复杂度是 $O({\log }_2^{2}k)$ 的。

在此之前，我们先引出一个新的概念：

• 异或空间

线性空间的推广。异或空间是关于异或运算封闭的整数集合。

类似地，我们也可以定义出异或空间的表出、线性相关和基：

表出：整数 $b$ 能够由整数 $a_1,a_2,\cdots ,a_k$ 异或得出，称 $b$ 能够被 $a_1,a_2,\cdots ,a_k$ 表出，也称 $b$ 为 $a_1,a_2,\cdots ,a_k$ 的线性组合；

同时也线性相关：任选异或空间中的若干个整数，如果其中存在一个整数能够被其它整数表出，则称这些整数线性相关，否则线性无关；

基：对于异或空间 $V$，若存在一个线性无关子集 $\mathfrak{B}$ 能够张成 $V$，称 $\mathfrak{B}$ 为 $V$ 的基，它仍然满足线性空间中基的三条性质。

接下来我们来看看线性基 $\mathfrak{B}$ 的构建方式。

考虑一个个加入 $A_i$，保证 $\mathfrak{B}$ 线性无关的同时需要保证 $A_i$ 能够被前面加入的 $A_1,A_2,\cdots A_{i-1}$ 表出。

inline void Build()
{
    for(register int i = 1; i <= n; i++)
    {
        if(!a[i]) { Zero = true; continue; }
        for(register int j = MAXLOG - 1; j >= 0; j--)
        {
            if(a[i] >> j & 1LL)
            {
                if(b[j]) a[i] ^= b[j];
                else
                {
                    b[j] = a[i], ++cnt;
                   	for(register int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1LL)) b[j] ^= b[k];
                    for(register int k = j + 1; k < MAXLOG; k++) if (b[k] >> j & 1LL) b[k] ^= b[j];
                    break;
				}	
			}
		}
	}
    return;
}

我们发现，这个程序和原来的构造方式有很多相似之处。

如果从线性代数的角度理解，可以发现，在线性基插入的过程中，我们相当于维护了一个上三角矩阵，满足主对角线下方的位置均为 $0$。

首先我们从大到小枚举 $A_i$ 的每一位，如果这一位上 $A_i$ 为 $1$ 并且矩阵主对角线的该位置已经有数，说明这一位可以被已经插入的数表出，为了维护上三角矩阵的性质，我们需要异或当前的数，使得 $A_i$ 继续往低位搜索的时候，我们可以不必再考虑高位。否则，我们为了能够使线性基中的数表出 $A_i$，就必须把 $A_i$ 放到当前这一位。

唯一不同的是多出了这两行：

for(register int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1LL)) b[j] ^= b[k];
for(register int k = j + 1; k < MAXLOG; k++) if (b[k] >> j & 1LL) b[k] ^= b[j];

这两行模拟的正是高斯消元的过程：用下面的行消掉这一行，再用这一行消上面的行。

为什么要这样维护呢？

我们来模拟这样一个过程吧：加入 $7,5,2,3$ 五个数到线性基中。

首先，加入 $7$ 时矩阵是没有任何数的，所以我们直接插入即可：
$$\left[\begin{array}{ccc}1& 1& 1\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$$
此时做高斯消元不会对整个矩阵有任何影响。

然后，加入 $5$ 时，可以发现第 $1$ 行已经被占据了。我们直接异或上这一行的数 $7$，再进行插入：
$$\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$$
当第 $2$ 行插入时，我们需要做高斯消元，然后矩阵就会变成：
$$\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$$
可以发现，这样异或后，整个矩阵仍然可以张成插入的数，不会有任何影响。

继续插入 $2$，会发现失败了，因为会被第二行异或为 $0$，实际上就表示了已有的 $7,5$ 可以表出 $2$；

然后插入 $3$：
$$\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$
进行消元会有：
$$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$
这个时候，我们显然可以发现：这个矩阵已经可以异或出插入的所有数了，同时，它也不能再插入任何数。

相信看到这里，你已经懂得了高斯消元的奥妙了。通俗地讲，高斯消元的作用在于：使每一位上的 $1$ 尽量地放到最低的位置。

我们还可以发现一个显然的性质：设线性基大小为 $cnt$，则其张成集的大小为 $2^{cnt}-1$。为什么会减 $1$？因为我们仍然需要特判 $0$ 的情况。

回到我们的初衷：求异或和的第 $k$ 小。我们发现，这样构建出的线性基就可以做二分了：

inline void Transform()	//把线性基中的数拎出来
{
    len = 0;
    for(register int i = 0; i < MAXLOG; i++) p[len++] = b[i];
    return;
}

inline LL Kth(LL k)
{
    if(Zero) --k;
    if(k >= (1LL << cnt)) return -1LL;	//查找失败
    LL res = 0LL;
    for(register int i = 0; i < cnt; i++) if(k >> i & 1LL) res ^= p[i];
	return res;
}

当然，对于这种构造方法，前面的三种操作同样适用。

贴上洛谷模板题代码：（非常作地用求第 $2^{cnt}-1$ 小来求最大值）

#include<iostream>
#include<cstdio>
#include<cstdlib>

#define MAXN 50

using LL = long long;
using namespace std;

int n, cnt;
bool Zero;
LL a[MAXN], b[MAXN], p[MAXN];

inline void Build()
{
	for(register int i = 0; i < n; i++)
	{
		if(!a[i]) { Zero = false; continue; }
		for(register int j = MAXN - 1; j >= 0; j--)
		{
			if(a[i] >> j & 1LL)
			{
				if(b[j]) a[i] ^= b[j];
				else
				{
					b[j] = a[i], ++cnt;
					for(register int k = j - 1; k >= 0; k--) if(b[j] >> k & 1LL) b[j] ^= b[k];
					for(register int k = j + 1; k < MAXN; k++) if(b[k] >> j & 1LL) b[k] ^= b[j];
					break;
				}
			}
		}
	}
	int len = 0;
	for(register int j = 0; j < MAXN; j++) if(b[j]) p[len++] = b[j];
	return;
}

inline LL Kth(LL k)
{
	if(Zero) --k;
	if(!k) return 0LL;
	LL res = 0LL;
	for(register int i = 0; i < cnt; i++) if(k >> i & 1LL) res ^= p[i];
	return res;
}

int main()
{
	scanf("%d", &n);
	for(register int i = 0; i < n; i++) scanf("%lld", a + i);
	Build();
	printf("%lld\n", Kth((1LL << cnt) - 1 + Zero));
	return 0;
}

看到这里，你应该已经知道了：线性基的插入操作是基于高斯消元法的。

正因为如此，线性基还有一个作用：求异或方程组解的个数。

• 例题：

​ 给出若干个形如 $x_{p_1}\mathrm{xor}{x}_{p_2}\mathrm{xor}\cdots \mathrm{xor}{x}_{p_m}=0$ 的方程，求解的个数。

​ 其中 $x_{1\sim n}$ 为 $0$ 或 $1$，$p_{1\sim m}$ 是一个长为 $m$ 的单调上升序列，满足 $\forall i\in [1,m],1\le p_i\le n$。

答案为 $2^{cnt}$ ，其中 $cnt$ 表示线性基中值为 $0$ 的位置个数。

我们来思考值为 $0$ 的位置代表了什么：

假设这个位置代表的位为 $i$，那么每一次插入一个方程时，线性基会通过已有的方程对其进行高斯消元。

如果第 $i$ 位上的数为 $0$，说明每一次插入时，$x_i$ 都会被已有的方程给消元。换言之，已有的方程通过互相异或，可以消去 $x_i$ 这个元。

这样的话，$x_i$ 可以取到在值域里的任何值，同时线性基中所有值不为 $0$ 的位置代表的元都会有对应的取值。

根据线性代数的定义，前者叫做自由元，后者叫做主元。

如果清楚高斯消元法的定义，那么可以得知：高斯消元法的解的个数取决于自由元的解的个数，每一组自由元的解都会决定剩下的所有主元的解。

所以答案就呼之欲出了：解的个数即为 $2^{cnt}$，$cnt$ 为自由元的个数，在线性基中的体现即为值为 $0$ 的位置。

$ToBeContinued\cdots \cdots$