admin 的博客
线性基小记
admin LV 10 SU @ 2026-7-10 10:06:58

线性基小记更新于 2026/7/8 17:06:53 作者

command_block

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)$ 。

下面就是市面上常见的线性基构造代码：

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]装备购买
最大子集异或值 ： P3812 【模板】线性基

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]彩灯。

关于有没有 $0$ ，需要一次特判。

将三角基消成对角基，然后将 $k$ 拆位，从高到低对应到线性基中出现的位上。

答案就是对应位上的向量的异或和。

证明仍然可以沿用二进制按位贪心的思想，这里就不再赘述了。

线性基合并

由于线性基中只会有 $O(k)$ 个元素，将其中一个线性基暴力插入另一个即可，复杂度为 $O(k^2)$ 。

注意，线性基可能不满，适当的剪枝能够带来可观的效率提升。

例题 :

例题① ： P4869 albus就是要第一个出场

题意：将一个集合 $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和路径

题意：给出一张带权无向图，求 $1,n$ 之间的异或和最小的路径（允许自交）。

由于异或的自反性，可以发现一些很好的性质：在 $u,v$ 之间来回走两次，答案不变。

那么，可以视作我们能在两点之间任意传送，但是要按时回来。

这样，可以想象，路径一定是若干个简单环和 $1,n$ 之间的一条简单路径。（具体见其他题解）

那么，将所有环的 $\rm xor$ 值建立一个线性基，然后求出其与 $1,n$ 之间任意一条路径异或值的最大异或和即可。

问题在于，简单环的个数可能非常多，无法一一找出。

一个经典的做法是：求出该图的一个生成树，然后只考虑所有包含一条非树边的环。

由自反性，包含多条非树边的环一定可以由若干只包含一条非树边的环拼出来。

带修版本：CF938G Shortest Path Queries

带删除线性基
强制在线

用线段树配合线性基合并不难做到 $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]元素

求最大权线性基的权值和。按照权值排序然后逐次尝试加入，正确性同 $\rm Kruskal$ 。

例题④ : CF1100F Ivan and Burgers

可以用线段树/猫树配合线性基合并做到 $O(k^2\log n)$ 或者 $O(k^2)$ 的复杂度。

让每个元素的权值定为其出现位置，逐渐加入元素时，求出最大权值线性基。

询问区间 $[l.r]$ 时，查看 $r$ 时刻得到的最大权值线性基，将其中权值未达到 $l$ 的基抛弃，则为 $[l,r]$ 的线性基。

线性基小记

0.前置芝士

1. $\rm OI$ 中的线性基

状态

开发

支持

关于

线性基小记

0.前置芝士

1.OI\rm OIOI 中的线性基

状态

开发

支持

关于

还没有账户？

登录

1. $\rm OI$ 中的线性基