线性基小记

## 0.前置芝士 非必须知识，若对线性基已经比较熟悉，或有一定感性理解，可以选择性跳过。 和线性代数有关。目前还比较简略，建议配合其他资料食用。 - **线性组合** 简单来说就是几个东西加权（数乘）之后加在一起。 - **线性有关/无关** 一组向量线性无关 $\Leftrightarrow$ 没有向量可用有限个其他向量的线性组合所表示。 - **张成** 向量集合 $V$ 的所有线性组合形成的集合 $S$ 称作 $V$ 的张成空间，记作 ${\rm span}(V)$ - **基** 若向量集合 $B$ 线性无关，则称 $B$ 是 ${\rm span}(B)$ 的一组基。 比如，三维空间可以以空间直角坐标系的三个轴（的方向向量）作为基。 - 性质 - $B$ 的任何真子集都不是 ${\rm span}(B)$ 的基。 由 $B$ 线性无关，任意去掉一个向量，其余的都无法将其拼（线性组合）出来，显然也无法张成原来的 ${\rm span}(B)$ - ${\rm span}(B)$ 中所有的向量都可以按唯一的方式表达为 $B$ 中向量的线性组合。 若有两种不同的方案，相减之后则可得出 $B$ 线性有关，矛盾。 - 空间 $S$ 所有的基集合的大小都是相同的，且恰好等于 $S$ 的维度。(显然) - **线性相关引理** 若向量集合 $V$ 线性相关，存在 $B\subsetneq V$ 使得 ${\rm span}(B)={\rm span}(V)$ 人话说就是，丢掉一些向量，张成空间不会变化。 具体地说，随便找出一组线性相关关系，丢掉任意**一个**，则可以用剩余的来表示丢掉的那一个。 # 1.$\rm OI$ 中的线性基 在 $\rm OI$ 中，“线性基” 专用于解决有关异或的一些问题。 异或运算可以看做 $\bmod\ 2$ 意义下的向量加法。 类似地，我们定义 ${\rm span}(S)$ 为数字集合 $S$ 的所有子集的异或和组成的集合。 方便起见，设本文中涉及的二进制数位长为 $k$ ，且不超过计算机位长 $w$。 - **张成空间判定问题①** 给出一个**线性无关**的二进制数集合 $B$ ，判定数 $a$ 是否在 ${\rm span}(B)$ 中。 不难发现 $B$ 就是 ${\rm span}(B)$ 的一组基整个空间是 $k$ 维（位）的，显然有 $|B|\leq k$。 $a\in{\rm span}(B)\Leftrightarrow $ 存在一个 $B$ 的线性组合$=a$ ,即 $a,B$ 线性有关。 可以把 $a,B$ 放在一起进行消元，若能消出空行，则线性有关，反之则线性无关。 在消元时，不必按部就班写 $O(k^3)$ ，可以使用位运算 ($\rm xor$) 优化，复杂度为 $O(k^2)$。 - **张成空间判定问题②** 题意同上，但询问 $q$ 次。 考虑通过适当的预处理将询问的复杂度降低。 将 $B$ 预先削成上三角矩阵（~~三角基~~），这样，加入一行之后，只需要 $k$ 次行间操作即可。 这样的复杂度是 $O(k^2+qk)$。 - **基的求解** 给出一个二进制数集合 $V$ ，求 ${\rm span}(V)$ 的一组基。 采用增量法，逐个加入向量，同时维护基。 新加入一个向量时，若已经能够被之前的基拼（线性组合）出来，则不加入。 复杂度为 $O(|V|k)$。 下面就是市面上常见的线性基构造代码 ： ```cpp struct Linear_Base { ll a[62]; void add(ll x) { for (int i=60;i>=0&&x;--i) if (x&(1ll<<i)){ if (a[i]) x^=a[i]; else { a[i]=x; break; } } } }; ``` `a[i]` 存放最高位为 `i` 的基向量。 加入新的向量时，从高位到低位枚举。 若 `x` 已有某位，且基中也有某位，则消去该位。 否则，该位不可能被消去，将 `x` 加入线性基。过程结束。 - 实数线性基 ： [P3265 [JLOI2015]装备购买](https://www.luogu.com.cn/problem/P3265) - **最大子集异或值** ： [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812) ```cpp ll qry(ll x) { for (int i=60;i>=0;i--) if ((x^a[i])>x)x=x^a[i]; return x; } ``` `qry` 函数可以求 $x$ 与线性基的最大异或和，本题中，`qry(0)` 就是答案。 这段代码的意思是 : 从高位到低位考虑基，若异或后变大，则异或。 正确性说明 : 由于 $a[0..i-1]$ 都不含 $i$ 及以上的位，其最大贡献仅为 $2^i-1$。 - 若此时 $x$ 的第 $i$ 位是 $0$ ，则异或上 $a[i]$ 至少带来 $2^i$ 的收益，大于后面可能的所有收益。 同时，`(x^a[i])>x` 也必然成立。 - 若此时 $x$ 的第 $i$ 位是 $1$ ，至少在这一位有 $2^i$ 的亏损，大于后面的位可能的所有收益。 同时，`(x^a[i])>x` 也必不成立。 也有另外一种做法，首先将三角基进一步消成对角基，然后直接输出所有元素的异或和即可。 原理和上面的按位贪心是类似的，只不过第二种情况不会出现。 - $\bf k$**小子集异或和** (本质不同) 若原有的 $V$ 本就是线性无关的，则异或不到 $0$ ，能得到的异或值也就只有 $2^{|B|}-1$ 个。（有时允许选空集则无需考虑这种情况） 反之，能得到 $0$ ，则为 $2^{|B|}$ 个。 附 : 利用这个小结论即可做掉 [P3857 [TJOI2008]彩灯](https://www.luogu.com.cn/problem/P3857)。 关于有没有 $0$ ，需要一次特判。 将三角基消成对角基，然后将 $k$ 拆位，从高到低对应到线性基中出现的位上。 答案就是对应位上的向量的异或和。 证明仍然可以沿用二进制按位贪心的思想，这里就不再赘述了。 - **线性基合并** 由于线性基中只会有 $O(k)$ 个元素，将其中一个线性基暴力插入另一个即可，复杂度为 $O(k^2)$。 注意，线性基可能不满 ，适当的剪枝能够带来可观的效率提升。 例题 : 1. [P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292) 2. [P4839 P哥的桶](https://www.luogu.com.cn/problem/P4839) 3. [P5607 [Ynoi2013]无力回天NOI2017](https://www.luogu.com.cn/problem/P5607) - **例题①** ： [P4869 albus就是要第一个出场](https://www.luogu.com.cn/problem/P4869) **题意** ： 将一个集合 $V$ 的所有子集异或和排序（不去重），问某个数的排名。 若去重，则不难转化成前面的 $k$ 小异或和问题。 结论 : 有 $2^{|B|}$ 种异或值，每个异或和都出现次数相同，为 $2^{|V|-|B|}$。 证明 ：首先选出 $B$ 的一个子集异或值 $s$，考虑拼出 $s$ 的方案数。 可以在 $V-B$ 中选择一个子集 $S$ ，$S$ 中的每个向量都能被 $B$ 拼出来，所以 $S$ 的任意子集异或和都能被 $B$ 拼出来。 $S$ 的子集有 $2^{|V|-|B|}$ 个。这就证明了对于每种本质不同的异或和，至少有 $2^{|V|-|B|}$ 种方案。 由于总方案数为 $2^{|V|}$ ，显然这个下界是紧的。 有了上述结论，只需要将求出的排名乘以 $2^{|V|-|B|}$。 - **例题②** : [P4151 [WC2011]最大XOR和路径](https://www.luogu.com.cn/problem/P4151) **题意** ： 给出一张带权无向图，求 $1,n$ 之间的异或和最小的路径（允许自交）。 由于异或的自反性，可以发现一些很好的性质 ： 在 $u,v$ 之间来回走两次，答案不变。 那么，可以视作我们能在两点之间任意传送，但是要按时回来。 这样，可以想象，路径一定是若干个简单环和 $1,n$ 之间的一条简单路径。（具体见其他题解） 那么，将所有环的 $\rm xor$ 值建立一个线性基，然后求出其与 $1,n$ 之间任意一条路径异或值的最大异或和即可。 问题在于，简单环的个数可能非常多，无法一一找出。 一个经典的做法是 ： 求出该图的一个生成树，然后只考虑所有包含一条非树边的环。 由自反性，包含多条非树边的环一定可以由若干只包含一条非树边的环拼出来。 带修版本 ：[CF938G Shortest Path Queries](https://www.luogu.com.cn/problem/CF938G) - **带删除线性基** - 强制在线 用线段树配合线性基合并不难做到 $O(k^2\log n)$，在此不叙。 我们维护一个**不经消元**的线性基，以及所有不在线性基内的数。 假设我们要删除 $u$。 如果 $u$ 不在线性基内，直接删掉即可。 若 $u$ 恰好在线性基内，则需要进行讨论。 对于某个不在线性基中的数 $x$，必有且仅有一个线性基的子集 $S$ 异或和为 $x$ ,记为 $S_x$。 假如线性基外的某个数 $x$ 的 $S_x$ 中包含 $u$，那么就说明 $S_x,x$ 是线性相关的。 此时用 $x$ 替换 $u$ 并将 $u$ 删除即可。（若找不到这个 $x$ 就直接删除 $u$） 然后要维护 $S$ ，由于 $u$ 被新的 $x∩(S_x-u)$ 代替了，而且原来 $u$ 的位置被 $x$ 占据了，这相当于让所有含有 $u$ 的 $S_y$ 异或上 $(S_x-u)$。 由于原来是 $u$ 现在是 $x$ 这一位没有变，我们可以把“让所有含有 $u$ 的 $S_y$ 异或上 $(S_x-u)$”这条指令拆分成 $O(k)$ 条“让所有含有 $u$ 的 $S_y$ 的某一位取反”这样的指令。 咕。 - 离线 显然可以套用线段树分治得到 $O(k\log n)$ 的复杂度。 实际上可以做到 $O(k)$ 。 对于每个元素，记下其删除时间。 先考虑**不经消元**的线性基。 当加入一个新向量时，若和旧的基线性无关，则直接加入。 若和旧的基线性有关，则可以在线性有关的一组向量中换掉一个。 类似动态生成树等问题，我们尝试用删除时间晚的去换早的。这称作**最大权线性基**。 然而每次都要消元，复杂度 $O(k^2)$ ，并不优越。 ------------ 考虑沿用前面的思路削成三角基。设 $h_x$ 为 $x$ 的删除时间。 我们尝试构造一种方案，使得消元之后，线性基中的 $h$ 不会变差。 在消元时，$\{x,y\}$ 可以被 $\{x,x\ {\rm xor}\ y\}$ 代替。若本体 $x,y$ 的其中一个被删去，则由它们产生的 $x\ {\rm xor}\ y$ 也会失效，即 $h_{x\ {\rm xor}\ y}=\min(h_x,h_y)$。 这样，不难想到将基按照 $h_x$ 从大到小排序，然后用前面的消后面的。这样，所有位置上的 $h$ 都不会变小。 ------------ 以上是把任意基变成三角基的 $O(k^2)$ 消元，接着考虑增量法。 我们让已有的三角基以 $h$ 为序，若 $u$ 和基线性无关，则可加入。 将 $u$ 以插入排序的方法加入,然后消元。不难发现，只有可能从 $u$ 向后消（传火?）,这样就是每次 $O(k)$ 的了。 ------------ 还有一种市面上流传较广的做法 ： 在 $u$ 加入（三角）线性基时，可能需要与某个向量 $a$ 异或（$u,a$ 的某一位都为 $1$）。 此时，若 $h_u>h_a$ 我们用 $u$ 替换 $a$。拿 $u\ {\rm xor}\ a$ 继续消。 - **例题③** : [P4570 [BJWC2011]元素](https://www.luogu.com.cn/problem/P4570) 求最大权线性基的权值和。按照权值排序然后逐次尝试加入，正确性同 $\rm Kruskal$。 - **例题④** : [CF1100F Ivan and Burgers](https://www.luogu.com.cn/problem/CF1100F) 可以用线段树/猫树配合线性基合并做到 $O(k^2\log n)$ 或者 $O(k^2)$ 的复杂度。 让每个元素的权值定为其出现位置，逐渐加入元素时，求出最大权值线性基。 询问区间 $[l.r]$ 时，查看 $r$ 时刻得到的最大权值线性基，将其中权值未达到 $l$ 的基抛弃，则为 $[l,r]$ 的线性基。