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

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

0%

线性基学习笔记

一些记号

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

  • $\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;
}
};

参考资料

姥爷们赏瓶冰阔落吧~