算法学习:线性基

算法学习:线性基

线性基 ——异或和求最大值

学习自博客:https://blog.sengxian.com/algorithms/linear-basis

基(basis)是线性代数中的一个概念,他是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素被称为基向量。向量空间中的任意一个元素,都可以唯一地被表示成基向量的线性组合。异或空间基向量,被称为线性基。

从线性代数开始的异或世界

线性空间(向量空间)

定义$({\Bbb F},\mathrm V,+,\cdot)$为线性空间(Vector Space)。其中 $\Bbb F$ 为域,其中的元素为标量;$\mathrm V$ 为集合,其中的元素称为向量,有以下两个运算:

  1. 向量加法:$\mathrm V+\mathrm V\rightarrow \mathrm V$,记作 ${\bf v}+{\bf w},\exists {\bf v},{\bf m} \in \mathrm V$;
  2. 标量乘法:${\Bbb F}\cdot \mathrm V\rightarrow \mathrm V$,记作 $a \cdot {\bf v}, \ \exists {\bf a} \in {\Bbb F},{\bf v}\in \mit \mathrm V$

且运算满足以下公理:

  1. 向量加法结合律:${\bf u} + ({\bf v} + {\bf w}) = ({\bf u} + {\bf v} ) + {\bf w}$;
  2. 向量加法交换律:${\bf v} + {\bf w} = {\bf w} + {\bf v}$;
  3. 向量加法的单位元:$\mathrm V$ 中有一个被称为零向量的 $\bf 0$,$\forall {\bf v}\in \mathrm V$,${\bf v} + {\bf 0} = {\bf v}$;
  4. 向量加法的逆元素:$\forall {\bf v}\in \mathrm {V}$,$\exists {\bf w} \in \mathrm V$,使得${\bf v} + {\bf w} = 0$,其中 ${\bf w}$ 称为 ${\bf v}$ 的逆元;
  5. 标量乘法与标量的域乘法相容:$a(b{\bf v} ) = (ab){\bf v}$;
  6. 标量乘法的单位元:域$\Bbb F$存在乘法单位元 $1$ 满足 $1{\bf v} = {\bf v}$;
  7. 标量乘法对向量加法的分配律:$a({\bf u} + {\bf v}) = a{\bf u} + a{\bf v}$;
  8. 标量乘法对域加法的分配律:$(a+b){\bf v} = a{\bf v} + b{\bf v}$。

基本性质

  • 零元素 $0$ 是唯一的;
  • 对任意的$a\in {\Bbb F}$,$a \cdot {\bf 0} = {\bf 0}$;
  • 对任意的${\bf u}\in \mathrm V$,${\bf 0}\cdot{\bf u} = {\bf 0}$( ${\bf 0}$ 是 $\Bbb F$ 的加法单位元);
  • 如果 $a \cdot {\bf u} = {\bf 0}$,则要么 $a = 0$ ,要么 ${\bf u} = {\bf 0}$;
  • 向量加法的逆向量 $\bf v$ 是唯一的,记作$-\bf v$。${\bf u} + {- \bf v}$ 也可以写成 ${\bf u} - \bf v$,两者都是标准的;
  • 对 $\forall {\bf u} \in \mathrm V$, $-1\cdot {\bf u}=-{\bf u}$。
  • 对 $\forall a\in \Bbb F$ 以及${\bf u}\in V$,$(-a)\cdot {\bf u} = -(a\cdot {\bf u}) = a \cdot (-{\bf u})$。

其他扩展内容

最为常见的向量空间的例子是给定了直角坐标系的平面:平面上的每一点 $P$ 都有一个坐标 $P(x,y)$ ,并对应着一个向量 $(x,y)$。所有普通意义上的平面向量组成了一个空间,记作 $\Bbb R^2$(因为每个向量都可以表示为两个实数构成的有序数组$(x,y)$。可以验证,对于普通意义上的向量加法和标量乘法,$\Bbb R^2$ 满足向量空间的所有公理。设所有普通意义上的平面向量记作 $\mathrm V$ ,则 ${\Bbb R}^2 = ({\Bbb R}, \mathrm V,+,\cdot)$。实际上,向量空间是 $\Bbb R^2$ 的推广。

对于通常意义上的多项式加法和标量乘法,所有系数为实数的多项式的集合 $\Bbb R[\bf X]$ 也构成一个向量空间。更广泛的,所有从实数域射到实数域的连续函数的集合 $\mathcal C(\mathbb R,\mathbb R)$也是向量空间

线性无关

对向量空间中 $\mathrm V$ 上的 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,若存在不全为 $0$ 的数 $a_i\in \mathbb F$,满足:
$$
a_1{\bf v}_1 + a_2{\bf v_2} + \dots + a_n{\bf v} _ n = 0
$$
则称 $n$ 个向量线性相关Linearly Dependent),否则称为线性无关Linearly Independent)。

线性组合

对于向量空间中 $\mathrm V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其线性组合Linear Combination)是如下形式的向量:
$$
a_1{\bf v_1} + a_2{\bf v}_2 + \dots+a_n{\bf v}_n
$$
其中 $a_1,\dots,a_n\in \mathbb F$。

张成(Span

对于相连空间中 $V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其所有线性组合所构成的集合称为 $({\bf v}_1,\dots,{\bf v}_n)$ 的张成Span),记作$\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$。

基(Basis)

Basis)(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数

给定一个向量空间 ${\displaystyle \mathrm {V}}$。${\displaystyle \mathrm {V}}$ 的一组 ${\displaystyle {\mathfrak {B}}}$ 是指 ${\displaystyle \mathrm {V} }$ 里面的可线性生成 ${\displaystyle \mathrm {V} }$ 的一个线性无关子集。${\displaystyle {\mathfrak {B}}}$ 的元素称为基向量

更详细来说,设 ${\displaystyle {\mathfrak {B}}={\mathbf e_{1},\mathbf e_{2},\cdots ,\mathbf e_{n}}}$ 是在系数域 ${\displaystyle \mathbb {F}}$(比如实数域 ${\displaystyle \mathbb {R}}$ 或复数域${\displaystyle \mathbb {C}}$)上的向量空间 ${\displaystyle \mathrm {V}}$ 的有限子集。如果 ${\displaystyle {\mathfrak {B}}}$ 满足下列条件:

  1. 对任意 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$ ,如果 ${\displaystyle \lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}=0}$ 则必然 ${\displaystyle \lambda _{1}=\lambda _{2}=\cdots =\lambda _{n}=0}$;
  2. 对任意 ${\displaystyle \mathbf v\in \mathrm {V} }$,可以选择 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$,使得 ${\displaystyle v=\lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}}$。

就说 ${\displaystyle {\mathfrak {B}}}$ 是向量空间 ${\displaystyle \mathrm {V} }$ 的一组

性质

设 $\mathfrak {B}$ 是向量空间 $\mathrm V$ 的基。则 $\mathfrak {B}$ 具有以下性质:

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

第三点尤其重要,感性的理解,基就是向量空间中的一个子集,它可以通过唯一的线性组合,来张成向量空间中所有的向量,这样就可以大大的缩小我们向量空间的大小。

线性相关性引理(Linear Dependent Lemma

如果 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq 0$,则有至少一个 $j \in {2, \ldots, m}$使得下列成立:

  1. $\mathbf{v}_j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{j - 1})$;
  2. 如果从$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项,则剩余向量组的张成仍然等于 $\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})$。

证明:

设 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq \mathbf{0}$,则有不全为 $0$ 的 $a_1, \ldots, a_n \in \mathbb F$,使得
$$
a_1\mathbf{v}_1 + \ldots + a_m\mathbf{v}_m = \mathbf{0}
$$
$a_2, a_3, \ldots, a_n$不会全为 $0$(因为 $\mathbf{v}_1 \neq \mathbf{0}$)。设 $j$ 是 ${2, \ldots, m}$ 中使得 $a_j \neq 0$ 的最大者,那么
$$
\mathbf{v}_j = -\frac {a_1} {a_j}\mathbf{v}_1 - \ldots - \frac {a_{j - 1}} {a_j}\mathbf{v}_{j - 1}
$$
这就有 $(1)$ 成立。

为了证明 $(2)$,设 $\mathbf{u} \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$,则存在 $c_1, \ldots, c_n \in F$,使得
$$
\mathbf{u} = c_1\mathbf{v}_1 + \ldots + c_n\mathbf{v}_n
$$
在上面的等式中,可以用之前的等式右边来代替$ \mathbf{v}_j$。这样 $\mathbf{u} $包含于从 $(\mathbf{v}_0, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项的张成,因而 $(2)$ 成立。

线性基

对于一个十进制数 $a$,我们将其转换为二进制得到 $(b_m\dots b_0)_2$。然后将转换后的二进制看作是一个向量,则得到$\mathbf a = (b_m,b_{m-1},\dots,b_0)$。方便起见,我们称向量 $\mathbf a$ 的第 $i$ 位为 $b_i$。

向量组 $\mathbf a_1,\dots\mathbf a_n$ 可以张成一个向量集合 $\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n)$,则可以得到一个线性空间 $\mathrm V = ({0,1},\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n),\oplus,\cdot)$。

按照以下的方法得到这个线性空间的一个基 $\mathfrak B = (\mathbf a_1,\dots,\mathbf a_n)$ :

第 $1$ 步:如果 $\mathbf a_1 = \mathbf 0$,则从 $\mathfrak B$ 中去除 $\mathbf a_1$,否则保持 $\mathfrak B$ 不变。

第 $j$ 步:如果 $\mathbf a_j \in \mathrm{span}(\mathbf a_1, \dots ,\mathbf a_{j - 1})$ ,则从 $\mathfrak B$ 中去掉 $\mathbf a_j$,否则保持 $\mathfrak B$ 不变。

经过 $n$ 步后终止程序,得到一个向量组 $\mathfrak B$。由于每一次去掉的项包含于前面诸向量的张成,到最后这个组 $\mathfrak B$ 仍然可以张成 $\mathrm V$。而且这一程序确保了 $\mathfrak B$ 中的任何向量都不包含于它前面诸向量的张成,根据线性相关性引理可知 $\mathfrak B$ 是线性无关的。于是 $\mathfrak B$ 是 $\mathrm V$ 的一个基。

利用高斯消元来判断向量能否被前面的向量张成,就可以写出下面的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX_BASE 63 // 当数据为long long型时,int型为31
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (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;
}
}
}
}4
}
  • b[]数组用来记录最后得到的基 $\mathfrak B$ ;a[]数组为起初的每一个数字,即 $\mathbf a_1,\mathbf a_2,\dots,\mathbf a_n$。
  • 虽然数组每一个位置存储的是一个int型数字,但实际上表示的是一个二进制向量,为了表述方便,我们称b[i]为数组b[]的第 $i$ 行。
  • 在第 $i$ 步时,从高到低考虑数 $a_i$ 为 $1$ 的二进制位 $j$,如果数组b[]中第 $j$ 行已经存在内容了,我们就不能将$a_i$ 加到b[]中第 $j$ 行这个位置。而为了保证未来加进去的基向量与其他基向量线性无关,将数 $a_i$ 与 $b_i$ 进行异或计算,就可以消掉可用已经存在的基向量来表示的部分。
  • 如果数组b[]中的第 $j$ 行不存在内容(内容为 $0$),则我们可以将(已经被前面步骤处理好的)数 $a_i$ 加入到这一行。此后为了维护对角矩阵,先用下面的行消自己,再用自己消上面的行。
  • 上面代码中,b[j] >> k & 1可以用来判断 $b_j$ 二进制的第 $k$ 位是否为 $1$。为什么需要& 1?如果没有这个操作,我得到的不仅仅是第 $k$ 的信息,& 1可以让结果只保留第 $k$ 位的信息。

我们来模拟一下这个过程。设 $n = 5$,$a = {7, 1, 4, 3, 5}$。矩阵 $\mathfrak B$ 一开始长这样:
$$
\begin{bmatrix}
0 &0 &0 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
我们从 $a_1$ 开始,$a_1 = 7 = (111)_2 = \mathbf a_1$,而 $\mathfrak B$ 目前为空。所以我就可以直接把他放进去了,因为$j = \mathrm{$MAX\_BASE} = 2$,所以我就把他放在了第二行(因为是上三角矩阵,所以最下面的为第 $0$ 行)。
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
然后考虑放$a_2$,$a_2 = 1 = (001)_2 = \mathbf a_2$,在 $j = 2$ 与 $j = 1$ 时都不满足a[i] >> j & 1的条件,所以不进行操作。$j = 0$ 时,第 $0$ 行没内容,所以就直接放在了第 $0$ 行上,于是矩阵就成了:
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的不存在下面的行。再用自己消上面的行,所以第 $2$ 行会消去最后一个 $1$,矩阵变成:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来就轮到了 $a_3$ 了,$a_3 = 4 = (100)_2 = \mathbf a_3$,在 $j = 2$ 时符合条件,但第 $2$ 行已经有内容了,所以我们进行 $a_3 = a_3 \oplus b_2$ 的操作,于是 $a_3$ 成了 $(010)_2$ 。$j = 1$ 时有一次满足条件,所以将他放在了第 $1$ 行上,于是矩阵成了:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的什么都消不了。然后用自己消上面的行,所以第 $2$ 行中间的 $1$ 被消掉了,矩阵变成了:
$$
\begin{bmatrix}
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来谁也进不去了,结束。

那既然已经知道了结果会是一个上三角矩阵为啥我不直接生成一个呢?因为最终生成的 $\mathfrak B$ 很有可能不是一个满的上三角矩阵,比如这个样子的:
$$
\begin{bmatrix}
1 &0 &1&0 \\
0 &1 &0 &0 \\
0 &0 &0 &0 \\
0 &0 &0 &1
\end{bmatrix}
$$
这样所有被选上的 $\mathbf a_i$ 构成了一个向量空间 $\mathrm V$ 的一个基 $\mathfrak B$,同样矩阵 $b$ 的每一个非 $\mathbf 0$ 向量 $\mathbf b_i$ 组成的基也是向量空间 $\mathrm V$ 的基。我们所指的线性基,特指高斯消元解出的对角矩阵的非零行构成的向量组。如果矩阵的主对角线上第 $i$ 行的元素为 $1$,此时我们称第 $i$ 位存在于线性基中。对于存在于线性基的二进制位,有一个重要的性质:
$$
对于任意存在于线性基的二进制位\ i ,至多只有一个\ \mathbf b_j\ 满足第\ i\ 位为\ 1。
$$
因为我们已经在得到线性基的过程中,不断地使用每一个向量来对上下进行消除,所以 $\mathbf b_j$ 一定消去了别的向量第 $i$ 位上的 $1$,所以二进制位 $i$ 只存在于 $\mathbf b_j$ 上。而对于不再线性基中的二进制位 $i$,那么主对角线第 $i$ 行位以下的全部为 $0$, 而上方就可能会有若干个 $1$。

线性基的应用

线性基的题型相对比较固定,以下几类基本就是线性基了:

  • 最大异或和
  • 第 $k$ 大异或和 / 这些元素的异或和是第几大
  • 求所有异或值的和

例题$(1)$ To xor or not to xor

题目连接:https://codeforces.com/problemsets/acmsguru/problem/99999/275

Description

The sequence of non-negative integers $A_1$, $A_2$, …, $A_n$ is given. You are to find some subsequence $Ai_1$, $Ai_2$, …, $Ai_k$ $(1 \leq i_1 < i_2 < … < i_k \leq N)$ such, that $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ has a maximum value.

Input

The first line of the input file contains the integer number $N$ $(1 \leq N \leq 100)$. The second line contains the sequence $A_1, A_2, \dots , A_n (0 \leq Ai \leq 10^{18})$.

Output

Write to the output file a single integer number – the maximum possible value of $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ .

Sample test(s)

Input
1
2
3 
11 9 5
Output
1
14

很单纯的求最大异或和。根据以上的内容,我们可以求出这个向量空间的一组线性基 $\mathfrak B$,则最大的异或和就是将线性基中所有的向量异或起来得到的向量所对应的数。证明如下:

最高的二进制位只存在于数值最大的基向量上,所以最大的基向量肯定要被选。运用归纳法,假设前 $i$ 大的都需要选,考虑第 $i + 1$ 大的向量选不选。显然第 $i + 1$ 大的基向量能对异或和贡献它的最高的二进制位 $j$,因为二进制位 $j$ 在之前的异或和中必然为零(因为二进制位 $j$ 只存在于第 $i + 1$ 大的基向量中)。如果不选,之后的所有数对答案的贡献都只能在小于这个二进制位的地方做贡献,总是比选 $i + 1$ 得到的答案小,所以这个数必须选。

AC代码:

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
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define MAX_BASE 63
long long a[101];
long long b[MAX_BASE];
int n;
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (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;
}
}
}
}
}
int main(){
scanf("%d" ,&n);
memset(b, 0, sizeof(b));
memset(choice, 0, sizeof(choice));
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
cal();
long long ans = 0;
for (int i = 0; i <= MAX_BASE; i++) {
if(b[i]){
ans ^= b[i];
}
}
printf("%lld\n", ans);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×