线性基 学习笔记
djwj233
2021-07-23 08:05:48
### 1. 线性空间的定义
**线性空间**（*linear space*. *a.k.a.* **向量空间**，*vector space*）是一个关于向量加法和标量乘法的封闭向量集合。
*注意*：这里的向量加法和标量乘法可以是**广义**的，如 OI 中广泛地将向量加法定义为异或。但它们需要满足**交换律**、**结合律**、**分配律**。
*e.g.*：$\forall n\in \mathbb N_+$，$R^n$ 是线性空间。（$R^n$ 定义为所有的 $n$ 维向量所构成的集合）
给定向量 $\bold a_{1\cdots k}$，若向量 $\bold b$ 能通过它们由向量加法和标量乘法得到，那么称 $\bold b$ 能被 $\bold a_{1\cdots k}$ **表出**（*linear expression*）。所有能被 $\bold a_{1\cdots k}$ 表出的向量构成一个线性空间，$\bold a_{1\cdots k}$ 是它的**生成子集**（*generating subset*）。
*e.g.*：若有 $\bold a_1=(2,3)$，$\bold a_2=(1,4)$，则 $\bold b=(4,11)=\bold a_1+2\bold a_2$ 可被二者表出。
若对于线性空间中的一些向量 $\bold a_{1\cdots n}$，$\exists k_{1\cdots n}\in \mathbb R$，且 $\exists 1\le i\le n，k_i\ne 0$，满足：
$$
\sum\limits_{i=1}^n k_i\bold a_i=0
$$
则称它们**线性相关**（*linearly dependent*），否则它们**线性无关**（*linearly independent*）。（此处定义和蓝书不同，下文将说明两种定义是一致的）
线性无关的生成子集被称为线性空间的**基底**（*basis*），简称**基**（*a.k.a.* **线性基**）。 基的大小成为线性空间的**维数**（*dimension*）。
*e.g.*：$\forall n\in \mathbb N_+$，$R_n$ 的一个基为 $\{(1,0,\cdots,0),(0,1,\cdots,0),\cdots,(0,0,\cdots,1)\}$，维数为 $n$，可记为 $\dim R_n=n$。
对一个 $n$ 行 $m$ 列的矩阵 $A$，以其 $n$ 个**行向量**为生成子集**张成**的线性空间的维数称为**行秩**，同样我们可以定义**列秩**。它们统称为**秩**（*rank*），记为 $r(A)$。
### 2. 线性空间的基本性质
- **性质：线性空间中存在零元（一个）、单位元（一个）、负元和逆元。**
证明：由封闭性易证。（简言之，**线性空间存在两种运算、四个元**）
- **性质：过原点的直线、平面（或者别的任意维空间）构成一个线性空间**。
证明：由空间的方程和线性空间的定义显然。
- **性质：对确定的线性空间任两个基的大小相等，均为维数**。
证明：考虑两组基 $\{\bold v_1,\bold v_2,\cdots,\bold v_n\}$，$\{\bold w_1,\bold w_2,\cdots,\bold w_m\}$。假设 $n\ne m$，由：
$$
\begin{cases}
\bold w_1=&a_{1,1}\bold v_1+&a_{1,2}\bold v_2+\cdots+&a_{1,n}\bold v_n\\
\bold w_2=&a_{2,1}\bold v_1+&a_{2,2}\bold v_2+\cdots+&a_{2,n}\bold v_n\\
\vdots&\vdots&\vdots&\vdots\\
\bold w_m=&a_{m,1}\bold v_1+&a_{m,2}\bold v_2+\cdots+&a_{m,n}\bold v_n\\
\end{cases}
$$
可得 $\bold w=\bold v A$，其中 $A$ 为所有的 $a$ 所构成的矩阵。同理有 $\bold v=\bold wB$。分别展开，有 $\bold w=\bold wAB$，$\bold v=\bold vAB$
由于 $\bold w$ 和 $\bold v$ 均线性无关，分别可得 $AB=I_n$，$AB=I_m$，产生矛盾。
综上，确定的线性空间维数唯一。
- **性质：$n+1$ 个 $n$ 维向量总是线性相关。**
证明：类似高斯消元法易知。
- **性质：向量 $\{\bold a_1,\bold a_2,\cdots,\bold a_n\}$ 线性相关的充要条件为其中的一个向量能被其余向量表出**。
证明：*必要性*：把定义式抄过来移项，将其中一个的系数除过去就能构造一组表示。*充分性*：把表达式移项，显然成立。
- **性质：若向量集合 $\{\bold a_1,\bold a_2,\cdots,\bold a_n\}$ 的一个部分组线性相关，则总体线性相关；若集合总体线性无关，则它的任意部分组线性无关**。
（也称**“部分相关，总体相关；总体无关，部分无关”**）
证明：由上一条性质易证。
- **性质：行秩 = 列秩**。
证明：将行空间进行行变换得到 $V_0$，有 $\dim C(A)=\dim V_0$。同理有 $\dim C(A^T)=\dim V_0$。
可得 $r(C(A))=r(C(A^T))$。（$C(A)$ 表示 $A$ 的行空间，$C(A^T)$ 表示 $A$ 的列空间）
- **性质：$r(AB)\le \min\{r(A),r(B)\}$**
证明：由于 $C(AB)$ 是 $C(A)$ 的一个子空间，因此有 $r(C(AB))\le r(C(A))$。（乘法的定义）
同理 $r(C(A^TB^T))\le r(C(B^T))$，$r(AB)\le \min\{r(A),r(B)\}$。
### 3. OI 中的线性基
在 OI 中，我们把每个数**根据其二进制**写为一个向量，**以这些数为生成子集**张成一个线性空间。
有线性基的定义及性质，可以轻易地导出以下结论：（摘自 OI-Wiki）
- 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。（定义 - 生成子集）
- 线性基是满足性质 1 的最小的集合。（性质 - 维数唯一）
- 线性基没有异或和为 0 的子集。（定义 - 线性无关）
- 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。（定义 - 线性无关）
**OI 中的线性基一般用于解决异或相关问题**。
那么，什么时候用 *01Trie* 呢？**一般来说，确定个数（一般为两个）的异或值考虑 *01Trie*，不确定个数的异或值考虑线性基**。
### 4. 线性基的计算
区别于上文讲的二进制意义下的线性基，这节里指的都是一般的线性基。（当然二进制意义下的线性基也可这么计算）
这样的线性基可以采用高斯消元的方式计算，我们一般采用行空间进行求解。
具体地，对于每一维，我们寻找当前此维值最大的一行，并指定其为线性基的一部分，进行消元：
```c++
fo(i,1,m) {
int cur=i;
fo(j,i+1,n)
if(fabs(a[cur][i])<fabs(a[j][i]))
cur=j;
fo(j,1,m) swap(a[i][j],a[cur][j]);
if(fabs(a[i][i])<=eps) continue;
fo(j,1,n) if(j!=i) {
db v=a[j][i]/a[i][i];
fo(k,1,m) a[j][k]-=a[i][k]*v;
}
}
```
消完元我们再遍历一遍所有的行，如果此行内所有的值都是 $0$，则由**高斯消元只执行初等行变换**可知此向量可被线性基中的数表出，反之则是线性基。
```c++
int cnt=0;
fo(i,1,n) {
bool flag=false;
fo(j,1,m) if(fabs(a[i][j])>eps) {
flag=true; break;
}
if(flag) cnt++;
}
```
上面代码中的`cnt`就是矩阵的秩。换言之，我们**可以用高斯消元在 $\Theta(n^3)$ 内求出矩阵的秩**。
如果要用高斯消元法求二进制意义下的线性基，消元的那个部分等价于整数的异或，这意味着它的复杂度此时是 $\Theta(n^2)$ 的。
### 5. 线性基的维护
对线性基的计算还有一种方式，就是采用**每次动态地把数加入线性基**的方式。
在 OI 中，我们一般默认**线性基中任意两个元素的二进制最高位不同**。若不然，可以将它们异或得到一个新数取代掉其中一个，这是等效的。
因此，我们可以对每个二进制位记录一个 $cur_i$，表示当前线性基中最高位为第 $i$ 位的数。
要插入一个数 $x$ 时，我们可以**从大到小**遍历每个二进制位：
- 如果 $x$ 在此位上为 $0$，那么它不能在这一位上产生贡献，直接忽略。
- 如果 $x$ 在此位上为 $1$，那么我们尝试将 $x$ 插入：
1. 假如此时 $cur_i=0$，直接将它赋值为 $x$。
2. 假如此时 $cur_i\ne 0$，根据上文提到的解决方法，我们它们异或得到一个新数取代掉其中一个。
这里取代掉 $x$，继续循环寻找能插入的位。
```c++
void insert(ll x) {
fr(i,55,0) {
if((x&(1LL<<i))==0)
continue;
if(cur[i]==0) {
cur[i]=x; break;
}
x^=cur[i];
}
}
```
如果要查询一个数 $x$ 是否在线性空间内，可以采用与插入类似的方法，从大到小遍历每个二进制位。
如果当前位为 $1$ 且 $cur_i=0$，说明**之后也肯定没有元素能抵消掉这一位**，直接判`false`。
否则就用 $cur_i$ 去异或 $x$，因为我们没有别的元素可以抵消这一位。
若程序运行到尾部，说明此时 $x$ 上的每一位都被抵消，返回`true`。
```c++
bool query(ll x) {
fr(i,55,0) {
if((x&(1LL<<i))==0)
continue;
if(cur[i]==0) return false;
x^=cur[i];
}
return true;
}
```
总复杂度 $\Theta(n\log x)$。**一般来说，这种做法优于高斯消元法，但只能支持二进制意义下的线性基**。
### 6. 例题
- [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812)（线性基模板）
板子题，直接把插入式线性基放上。那么怎么求最大值呢？
我们还是贪心地**从大到小**尝试异或上 $cur_i$ 的每一项。
```c++
fr(i,55,0) ans=max(ans,ans^cur[i]);
```
[Code](https://www.luogu.com.cn/record/53970234)
- [P3265 [JLOI2015]装备购买](https://www.luogu.com.cn/problem/P3265)（高斯消元式线性基模板）
也是板子，把高斯消元式线性基放上。
还有就是要注意精度 $eps$ 不能开太小，否则会有精度误差。我开了 $10^{-4}$ 就过了。
[Code](https://www.luogu.com.cn/record/53980622)
- [#114. k 大异或和](https://loj.ac/p/114)（经典题）
这题是经典题，有两种做法。
1. 蓝书上采用了高斯消元的方法。先一遍消元求出秩与线性基，然后贪心地加入答案。
不过复杂度高达 $\Theta(n^2\log a_i)$，这题显然超时。
2. 在网上搜到的做法，采用插入式线性基。
那么怎么保证 $k$ 大呢？还是采取原先的思想，如果当前答案异或上 $cur_i$ 会使答案变大，那么就认为**当前分支点中较大的一半是选择异或当前值的**，反之同理。
这样我们采用类似 *BST* 找 k 大时的操作即可。（不过要注意这里的第 $i$ 位并不一定是第 $i$ 层的分支点，需要先预处理一个 $pos_i$）
```c++
fr(i,55,0) if(cur[i]>0)
{
if(res<(res^cur[i])) {
if(k>=(1LL<<pos[i]))
k-=(1LL<<pos[i]), res^=cur[i];
} else {
if(k>=(1LL<<pos[i])) k-=(1LL<<pos[i]);
else res^=cur[i];
}
}
```
最后要注意特判一个 $0$。
[Code](https://loj.ac/s/1197039)
- [P4570 [BJWC2011]元素](https://www.luogu.com.cn/problem/P4570)（线性基的简单应用）
和板子也没差多少，高斯消元求一个线性基即可。
**千万要注意消元时循环起始点的位置不一定是 $i$，而是当前求出的秩的大小加一！**参考实现如下：
```c++
fo(i,0,62) {
int cur=-1;
fo(j,cnt+1,n) if(a[j]&(1LL<<i))
if(cur==-1||b[j]>b[cur])
cur=j;
if(cur==-1) continue;
cnt++;
swap(a[cnt],a[cur]), swap(b[cnt],b[cur]);
ans+=b[cnt];
fo(j,1,n) if(j!=cnt) if(a[j]&(1LL<<i))
a[j]^=a[cnt];
}
```
[Code](https://www.luogu.com.cn/record/54005478)
- [P4301 [CQOI2013] 新Nim游戏](https://www.luogu.com.cn/problem/P4301)（线性基与博弈论）
回顾一下 nim 游戏取胜的条件：**后手必胜当且仅当当前所有堆中的个数的异或和为 $0$。**
那么在这道题中，我们应当尽可能地让后手在第二回合取完以后异或和不为 $0$，这样先手才能必胜。
那么先手怎么取才能让后手在第二回合取完以后异或和一定不为 $0$ 呢？我们发现第二回合后的集合就是第一回合后的集合的一个子集，换言之，我们要保证第一回合后的集合的任意一个子集异或和均不为零。
**这就说明以第一回合后的集合是线性无关的，即它是一个线性基**。
这样就变成了一个线性基板子题。**一般来说，线性基在博弈论中的出现往往是 nim 游戏引出的**。
[Code](https://www.luogu.com.cn/record/54089806)
- [P4151 [WC2011]最大XOR和路径](https://www.luogu.com.cn/problem/P4151)（线性基与图论）
显然这题如果用 *01trie* 做空间、时间都会爆炸，可以用线性基来减小规模。
我刚开始的一个想法是像最短路那样去跑，但是这样可能会把两条从 $1$ 到 $i$ 的路径异或起来算成答案。
正确的做法应该是很神仙的，是**通过扩展仙人掌上的做法得到正解**。
具体地，我们找出一条从 $1$ 到 $n$ 的路径，然后用所有的环去增广它。由于从路径到环的一段会被走过两遍，因此**我们没有必要算出这个距离**。
那么怎么找环呢？我们 dfs 整棵树，对所有的返祖边、横叉边暴力统计即可。
**但是，这张图不是仙人掌，为什么这样是对的呢？**实际上，由于异或的性质，我们可以通过异或得到所有的简单环。
有一个注意点是从 $1$ 到 $n$ 的路径是必选的，不能和环的权值一样被加入线性基。
时间复杂度 $\Theta(m\log D)$。
[Code](https://www.luogu.com.cn/record/54131591)
事实上，如果求的不是最大值，而是对点对 $(u,v)$ 求所有路径的异或和的加和，则用拆位处理贡献的思路。**易证若线性基中此位为 $1$，则所有点对的加和均相等**。
见[CF724G Xor-matic Number of the Graph](https://www.luogu.com.cn/problem/CF724G)。
- [P5607 [Ynoi2013] 无力回天 NOI2017](https://www.luogu.com.cn/problem/P5607)（线性基与数据结构 / 维护区间线性基）
线性基显然没有办法满足区间可减性，但是可以实现快速合并，因此可以直接用线段树搞。
不过这个区间xor操作有点难搞，*Lazy-Tag* 也难传。基于这东西是区间可减的，我们可以大力差分。
令 $b_i=a_i \operatorname{xor} a_{i-1}$，单点修改就是改 $b_l$ 和 $b_{r+1}$，询问的话，由于 $a_i=\operatorname{xor}_{j=1}^i b_i$，因此：
**异或意义下，$\{a_{[l,r]}\}$ 与 $\{a_l\}\cup \{b_{[l+1,r]}\}$ 全等**。（因为异或可以把一些 $b_i$ 消去）
这样就好了（我可能做了个假的Ynoi）。时间复杂度 $\Theta(n\log n\log^2 a_i)$。
[Code](https://www.luogu.com.cn/record/54166760)（一发AC啊啊啊啊啊啊啊！！！）
- [CF1163E Magical Permutation](https://www.luogu.com.cn/problem/CF1163E)（线性基的灵活应用）
是一道 CF 风格的构造题，~~也是黑题~~ 掉紫了（大悲），非常神仙。（推完必要性发现不会做，看了题解awa）
我们先尝试求这个 $x$ 的值，再构造排列。
首先，其实`相邻两数的异或值`的本质就是差分，倒着转化为前缀和，那么相当于每个数就是由这些数其中的一些异或而成的。
**这说明，每个数都在由这 $n$ 个数张成的异或空间内**。那么我们求出这 $n$ 个数的线性基，枚举 $x$ 再逐一判断 $[0,2^x-1]$ 中的数，是否就行了呢？
hack：
```
2
4 5
```
按照上面的这个算法，$x$ 的值为 $1$。然而我们其实没法构造一个长为 $2$ 的排列。
问题正出在数的大小上：容易知道，如果这两个数是 ` 0 1`，那么它就合法了。我们发现，对于一个 $[0,2^x-1]$ 的排列，相邻两项的异或值小于 $2^x$。
那么我们把这 $n$ 个数排序，依次加入线性基中即可。这是对必要性的说明。
那么如何构造呢？根据线性基的性质，$[0,2^x-1]$ 中的每一个数都对应线性基的一个子集，且这些子集两两不同。
那么我们可以类似状压，用 $x$ 位二进制数对应线性基中的每个数是否被选。
由于前缀的性质，答案排列中相邻两位所对应的二进制**至多相差一位**。
这其实就是**格雷码**！也就是说，我们直接生成几个格雷码就行了。
最后要注意，这里线性基中的数不是 $cur$ 数组中存的数，而是插入的原始值。
[Code](https://www.luogu.com.cn/record/54183306)
完结撒花~~