隐藏
线性基学习笔记 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

线性基学习笔记

发表于 更新于 分类于 Valine：

一些记号

在本文中，为了描述方便，我们使用以下记号：

  • $\bigoplus$：异或。$2\bigoplus3=1$。
  • $\vec v$：向量，本文中的向量是抽象的数学概念，而非简单的带方向的数。

定义（们）

向量空间（vector space）

这里只是对向量空间进行严格定义，若不喜欢定义可以直接跳过。

给定域$F$，$F$上的向量空间$V$是一个集合，其上定义了两种二元运算满足八条公理。

  • 向量加法$+$：$V\times V\rightarrow V$，把$V$中两个元素$\vec u,\vec v$映射到$V$中的另一个元素，记为$\vec u+\vec v$。
  • 标量乘法$\cdot$：$F\times V\rightarrow V$，把$F$中的一个元素$a$和$V$中的一个元素$\vec u$变成$V$中另一个元素，记作$a\vec u$。

$F$中的元素称为标量，$V$中的元素称为向量。
一个满足要求的向量空间必须满足以下八条公理。（以下公理中，$\vec u,\vec v,\vec w$是$V$中的向量，$a,b$是$F$中的标量）

公理 说明
向量加法的结合律 $\vec u+(\vec v+\vec w)=(\vec u+\vec v)+\vec w$
向量加法的交换律 $\vec u+\vec v=\vec v+\vec u$
向量加法的单位元 存在一个称作零向量的元素$\vec0\in V$，使得任意$\vec v$满足$\vec v+\vec0=\vec v$
向量加法的逆元 对任意$\vec v\in V$都存在其逆元$\vec{-v}\in V$使得$\vec v+(\vec{-v})=\vec0$
标量乘法与标量域乘法互换 $a(b\vec v)=(ab)\vec v$
标量乘法的单位元 域$F$内存在乘法单位元$1$满足$1\vec v=\vec v$
标量乘法对向量加法的分配律 $a(\vec u+\vec v)=a\vec u+a\vec v$
标量乘法对域加法的分配律 $(a+b)\vec v=a\vec v+b\vec v$

若满足以上公理，我们记$(F,V,+,\cdot)$为向量空间。

线性相关（linearly dependent）与线性无关（linearly independent）

若向量空间$(F,V,+,\cdot)$中存在一组向量$\vec{v_1},\vec{v_2},\ldots,\vec{v_n}$，若域$F$中存在一组不全为$0$的数$a_1,a_2,\ldots,a_n$，使得：

即：

则称这组向量$\vec{v_1},\vec{v_2},\ldots,\vec{v_n}$线性相关，否则称这组向量线性无关。

线性组合（linear combination）

令$S$是向量空间$(F,V,+,\cdot)$的子集。
若存在一组向量$\vec{v_1},\vec{v_2},\ldots,\vec{v_n}\in S$，和对应的标量$a_1,a_2,\ldots,a_n\in F$，使得$\vec v=a_1\vec{v_1}+a_2\vec{v_2}+\cdots+a_n\vec{v_n}$，则称$\vec v$是$S$的线性组合。

一组向量线性无关$\leftrightarrow$这组向量中没有向量可以用其他向量的线性组合所表示

张成（linear span）

令$S$是向量空间$(F,V,+,\cdot)$中的一组向量$\vec{v_1},\vec{v_2},\ldots,\vec{v_n}$。
$S$所有线性组合所构成的集合为$S$的张成，记为$span(S)$。

形象地理解，张成就是一组向量扩展形成的空间。
如，两个不平行向量可以构成平面空间。

基（basis）)

若向量集合$V$中一组向量$\frak B$线性无关且能张成$V$，则称$\frak B$是$V$的一组基。

基与张成是相对的概念。
如，平面空间的基可以是任意两个不平行向量。

$\frak B$中的元素称为基向量。如果基中的元素有限，则称向量空间为有限维向量空间，将元素的个数称为向量空间的维度数。

基的性质

若$\frak B$是向量集合$V$的基，则$\frak B$具有以下性质：

  • $\frak B$的任何真子集无法张成$V$。
  • $V$中不含有其他包含$\frak B$的线性无关集合。
  • $V$中所有向量都可以唯一地表示为$\frak B$中向量的线性组合。

基的构造方式

随意选出一组向量$\vec{v_1},\vec{v_2},\ldots,\vec{v_n}$，依次检验每一个向量$\vec{v_i}$，若$\vec{v_i}$可以被表示为其他向量的线性组合，则去掉$\vec{v_i}$。
当这组向量中所有元素均被检验，留下的向量构成原向量空间的一组基。

线性基在信息学竞赛中的应用

线性基一般运用于在一类异或问题中。

异或线性基的定义

对于一组数$a_0,a_1,\ldots,a_n$，将$a_i$的二进制$(b_m\cdots b_0)_2$看做一个向量$\vec{a_i}=(b_m,\ldots,b_0)$。
向量组$\vec{a_0},\vec{a_1},\ldots,\vec{a_n}$可以张成一个向量集合$S=span(\vec{a_0},\vec{a_1},\ldots,\vec{a_n})$，加上异或运算与标量乘法即可形成向量空间$V=(\lbrace 0,1\rbrace,S,\bigoplus,\cdot)$。

异或线性基的构造

我们可以用上述基的构造方式的方法构造一组基。
即，每次判断$\vec{a_i}$是否属于$span(\vec{a_1},\ldots,\vec{a_{j-1}})$，若属于就不将$\vec{a_i}$加入基$\frak B$，否则加入。
注意，当$i=1$时判断$\vec{a_1}$是否等于$\vec0$。

我们可以用类似高斯消元的方法判断向量能否被前面的向量张成。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void add(LL num) {
	for(int j=MAX_BASE; j>=0; j--)
		if(num>>j&1) {
			if(b[j]) { //该位存在基向量
				num^=b[j];
				continue;
			}
			b[j]=num;
			for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
			for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
			break;
		}
}
void build(vector<int>a) {
	for(int num:a)add(num);
}

我们依次解释每一句代码的用途。
假设加入的数为$num$，以下所描述的第$j$位表示二进制的第$j$位，基第$j$位上的向量为$\vec{b_j}$。
称基矩阵为每一位的基向量二进制展开后得到的矩阵。

  1. 从高到低位依次检验第$j$位，若第$j$位为$1$则执行下列操作。

  2. 若第$j$位上已存在一个基向量$\vec{b_j}$，则将$num$异或$\vec{b_j}$。
    若该位已存在基向量，那么我们不能将$num$作为基向量放入该位，考虑将其放在更低的位。
    为什么要将$num$异或$\vec{b_j}$呢？首先，这样做是正确的，因为无论是否将其异或$\vec{b_j}$，张成是不会变的。对于解题来说，我们可以得到$num\bigoplus\vec{b_j}$这个数。其次，将其异或$\vec{b_j}$是为了使得基矩阵有优秀的上三角性质。

  3. 若第$j$位不存在基向量，且$num$当前第$j$位为$1$，此时应该将$num$作为基向量置入第$j$位。

  4. 为了维护一个近似对角矩阵，对于第$j$位后面的位$k$，若$num$第$k$位为$1$，则将$num$异或$\vec{b_k}$，同样用$num$异或前面位的向量。

我们举一个例子。
假设$n=6,a=\lbrace7,16,3,6,13,2\rbrace$
一开始基矩阵为空：

加入$7=(111)_2$，矩阵变为：

加入$16=(10000)_2$：

加入$3=(11)_2$：

为了维护近似对角矩阵，消去第三行的后两位，得到：

加入$6=(110)_2$，第三行已经有数，$6$被异或为$(010)_2=2$，第四行同样也有数，$2$被异或为$(001)_2=1$。

然后，矩阵变为：

用最后一行异或上面行得到：

加入$13=(1101)_2$，第二行没有数，直接加入，矩阵变为：

用下面的数异或第二行的数，得到矩阵：

接下来的数就加不进线性基了。
为什么称为类对角矩阵？
因为形成的矩阵不一定是一个对角矩阵，有可能非对角线也有$1$。

异或线性基的性质

对于最后得到的矩阵，若第$i$行主对角线上为$1$，我们称第$i$位存在于线性基中。

对于存在线性基的二进制位，有重要性质：
对于任意存在线性基的二进制位$i$，至多有一个$\vec{b_j}$满足第$i$位为$1$
证明：
我们用归纳法证明。

  • 对于第一个加入线性基的向量，显然其所在的列只有一个$1$。
  • 对于后加入线性基第$i$行的向量，对于$i$行后的所有行显然不会在第$i$列有数$1$，对于$i$前所有行若有$1$，经过异或操作可以将其消去。对于$i$行的其他位置所有的$1$都会被其下面行所消掉。因此，新加入一个向量同样满足性质。

利用数学归纳法可得，性质成立。

注意：上述过程我们将矩阵消成了类对角矩阵，如果只消成上三角矩阵则不具备该性质，但我们仍能知道哪些二进制位存在于线性基中。有时为了代码简便或时间效率，只消成上三角矩阵。

应用

求最大异或和

LibreOJ113 最大异或和
先求出线性基，然后将线性基全部异或起来即可。
正确性显然，此时的异或与或等价。

求k小异或和

LibreOJ113 k大异或和
我们可以利用二进制的思想得到$k$小异或和。

每个异或和出现次数

bzoj2844 albus就是要第一个出场
线性基有优秀的性质。
每个异或和出现次数均为$2^{n-\left|\frak B\right|}$。

求子集异或和的和

bzoj3811 玛里苟斯
因为线性基大小$\le63$，当线性基大小$\approx 20$时可以考虑枚举子集，再结合上述每个异或和出现次数即可得出答案。

模板

注意：线性基常常涉及long long范围，因此尽量不要使用1ll<<BASE，常常忘记ll，使用右移更不容易错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef long long LL;

const int maxn=20005,MAX_BASE=60;

struct Linear_Bases {
	LL b[MAX_BASE+5];
	Linear_Bases() {
		fill(b,b+MAX_BASE+1,0);
	}
	void add(LL num) {
		for(int j=MAX_BASE; j>=0; j--)
			if(num>>j&1) {
				if(b[j]) { //该位存在基
					num^=b[j];
					continue;
				}
				b[j]=num;
				for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
				for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
				break;
			}
	}
	void build(vector<int>a) {
		for(int num:a)add(num);
	}
	void merge(const Linear_Bases& b) {
		for(int i=0; i<=MAX_BASE; i++)
			if(b.b[i])add(b.b[i]);
	}
	LL cal() { //最大异或和
		LL ans=0;
		for(int i=0; i<=MAX_BASE; i++)ans^=b[i];
		return ans;
	}
};

参考资料

相关文章
姥爷们赏瓶冰阔落吧~