笔记重修计划三：线性基（施工中）

正在备战 THUWC，暂时停更。目前准备将这一系列内容迁移到 cnblogs。

本文属于笔记重修计划中的第三部，主要介绍广义的线性基与高斯消元的关联吗，以及在 OI 中应用较广的异或线性基。建议先阅读重修计划二 高斯消元（目前很需要施工故未公开）的内容。其实我觉得这两章的内容如果分开来看过于割裂了，之后可能会考虑在完善内容后合并一下的。

由于本人的数学知识只能勉强算个业余水平，所以有一些不太专业的语言请谅解/kt

广义的线性基与高斯消元

什么是线性基？对于一个向量集合 \(S\)，找出一个最小的基集合 \(B\)，使得 \(B\) 满足以下两条限制：

• \(B\) 内部线性无关，也就是说不存在 \(B\) 内某个元素能被其他元素线性表示出来。
• \(S\) 内的所有元素都能用 \(B\) 的元素线性表出。

而我们要找的线性基就是最小的满足上述限制的集合 \(B\)。

容易发现这和矩阵多少有点像。我们将 \(S\) 中的一个元素 \(\mathbf{v_i}=(a_{i,1},a_{i,2},\dots,a_{i,m})\) 写到矩阵上，那么 \(S\) 就能表示为一个 \(n\times m\) 的矩阵。我们要做的其实就是用已有的行去“消掉”一些无用的行，最后剩下一些最精简的有用行，就会是我们想要的线性基。其实这已经很像高斯消元了，我们先介绍一些矩阵、消元相关的概念，其实知道了这些概念之后会更好理解：

1. 增广矩阵：对于将线性方程组的系数写成矩阵，将系数矩阵右边加一列方程的常数项，这就是增广矩阵。
2. 矩阵初等行变换：分为三种，其实就是我们高斯消元中加减消元的方式：
   1. 交换两行。
   2. 给某一行乘上一个非 \(0\) 常数。
   3. 给某一行加上另一行的倍数。
3. 主元：在高斯消元的时候，目前在消未知数 \(x_j\)，那么我们会从当前操作行 \(cur\sim n\) 中选出一行作为主元（一般会选取 \(x_j\) 系数绝对值最大的一项以减小误差，保证数值稳定，在异或、同余方程中选出系数不为 \(0\) 的一行也行），然后将它交换到操作行 \(cur\)，其他 \(cur+1\sim n\) 行都通过矩阵初等行变换消掉 \(x_j\) 的系数。
4. 自由元：假如我们目前在处理变量 \(x_j\)，但是第 \(cur\sim n\) 行中 \(x_j\) 系数都是 \(0\)，此时 \(x_j\) 就是一个自由元，自由元的出现代表着出现了线性相关的式子，如果是对于方程而言，若最后消完了该行满足系数全 \(0\) 常数项非 \(0\) 那么无解；否则如果系数全 \(0\) 常数项也为 \(0\) 说明出现了多组解。假设每个变量有 \(V\) 中取值并且一共有 \(cnt\) 个自由元，那么一个有解的方程解的组数为 \(V^{cnt}\)。
   我们发现，在之前高斯消元的内容中介绍了 P2455 的消元方式，它灵活运用了矩阵初等行变换，当遇到了自由元 \(x_j\) 时，我们选择不消 \(x_j\)，但是 \(cur\) 仍然不变，目的就是看 \(cur\) 是否就是一个无用的向量，方便将它的系数全部消成 \(0\)。所以如果我们这样消元，记录当前操作行 \(cur\)，那么第 \(cur\sim n\) 行就都是自由元了（这里的 \(cur\) 是下一个要操作的行，所以它在消元完之后实际是操作的最后一行的下一行）。
5. 关键元：每行的第一个非零元，正常来说第 \(i\) 行的非零元就应该是 \(i\)，但是如果在第 \(1\sim i\) 列中出现了自由元，那么关键元就会变小（讲真的我不知道这个东西有啥用的说）。

介绍完了这些基本概念，我们再来思考构造线性基的方式就水到渠成了（前提是明白了 P2455 中的高斯消元方式）。我们只需要将向量列成 \(n\times m\) 的矩阵形式，用一样的消元方式，最后得到的线性基其实就是第 \(1\sim cur-1\) 行的向量。

给出一个简单的模板题 P3265 [JLOI2015] 装备购买，这里要我们求出权值总和最小的线性基，消元时直接取系数不为 \(0\) 且权值最小的向量作为主元，那么最后求出的系数非 \(0\) 行就是线性基中的向量。需要注意精度误差，由于高斯消元掉精严重，所以 \(eps=10^{-5}\) 比较合适，判为 \(0\) 的时候判绝对值是否 \(>eps\) 即可。需要注意在交换两行时要顺便把这两个向量对应的权值也交换了。

Submission.

异或线性基：从插入一个数，动态维护开始

异或线性基是一种特殊的线性基，我们将每个二进制数位看作向量的每个维度，原先的运算法则是逐维相加，现在改为逐维异或。按照高斯消元构造的线性基虽然常数更大，但是拥有消元后的增广矩阵拥有的主元、自由元对应的诸多性质，在一些应用中表现更好，且时空复杂度与市面上广传的线性基仍然相同。

回忆一下，线性基有两个基本要求：原数集 \(S\) 中的数都可以用线性基中某个子集凑出来；线性基内部线性无关。这种线性基可以看作一个高斯消元矩阵的形式，如果该列在 \(a_{i,i}\) 处有了一个主元，那么其他行就不能在第 \(i\) 列有值；否则它就是一个自由元，在别的行也能有。

就相当于我们将所有数二进制拆分后按位列成一个 \(n\times |B|\) 的矩阵，这里 \(|B|=\mathcal{O}(\log V)\)，相当于二进制数位的值域（维度数量），然后消元构造线性基，只是我们要利用异或的特殊性质来支持动态插入 \(S\) 中元素，而不是单纯的静态消元构造。

考虑对每一个二进制位（列）维护一个主元 \(b_i\)，整个线性基就是 \(B\)。我们说 \(B\) 中有 \(i\) 的主元当且仅当 \(b_i\ne 0\)。根据高斯消元矩阵的性质，我们列出这个线性基的一些要求：

• 如果 \(b_i=0\)，也就是说 \(i\) 是一个自由元，那么也要满足只有 \(j>i\) 的 \(b_j\) 在第 \(i\) 个二进制位为 \(1\)。
• 否则，要满足三个条件：
  1. \(b_i\) 低于 \(i\) 的二进制位可能为 \(1\)，这就是该位对应了一个自由元的情况，而若一个低于 \(i\) 的已经存在于 \(B\) 中的二进制位，它就必须为 \(0\)。
  2. \(b_i\) 中高于 \(i\) 的二进制位一定为 \(0\)，也就是 \(i\) 是 \(b_i\) 的最高位。
  3. 整个 \(B\) 中除了 \(b_i\) 以外没有别的元素第 \(i\) 个二进制位为 \(1\)。

考虑我们怎么在插入新的数的时候动态构造线性基并保证原先的性质。插入一个数，相当于要看它是否能被线性基内的数凑出来，如果有一些位凑不出来，那么需要在这些位上做改动，利用 \(x\) 求出它们新的 \(b\)，同时还要对一些别的元素做改动，以保证线性基的两个性质。假如现在我们插入一个数 \(x\)，从大到小枚举二进制位 \(i\)，假如 \(x\) 在第 \(i\) 位为 \(0\)，跳过它；否则：

• 如果 \(b_i\) 已经有值了，那么直接将 \(x\) 异或上 \(b_i\) 表示在凑 \(x\) 的过程中一定要用上 \(b_i\)（为什么呢？由于这种线性基的性质：\(b_i\) 有值说明 \(i\) 是一个主元，那么 \(B\) 中除了 \(b_i\) 就不会有别的元素在第 \(i\) 个二进制位上有值，所以不在这里消也没有办法再消）。

• 否则说明出现了一个原本是自由元的位置，但是现在它需要变成一个主元。为了要满足这个主元的性质，我们要对 \(x,B\) 中其他数做一些改动再将 \(x\) 放到 \(b_i\)：

  1. \(x\) 中低于 \(i\) 的已经存在于线性基中的二进制位一定为 \(0\)。这种情况需要枚举每个 \(j<i\)，如果 \(x\) 在第 \(j\) 位为 \(1\)，那么 \(x\) 要异或上 \(b_j\)。而显然此时 \(b_j\) 是已经存在了的。
  2. \(b_i\) 中高于 \(i\) 的已经存在于线性基中的二进制位一定为 \(0\)。发现这种情况不用管，因为我们是从大到小遍历 \(i\)，如果有这样的位 \(x\) 早就异或上 \(b_j\) 消掉了。
  3. 整个 \(B\) 中除了 \(b_i\) 以外没有别的元素第 \(i\) 个二进制位为 \(1\)。这个考虑两种情况：
     • 对于 \(j<i\)，如果 \(b_j\) 中第 \(i\) 个二进制位为 \(1\)，那么它就不会被插入到 \(b_j\) 上了，因为一个主元需要满足其最高位为它对应的那个二进制位，自由元对应的位就算是 \(1\) 也只能在它自己对应的二进制位之下了。所以不需要考虑这种情况。
     • 对于 \(j>i\)，不保证 \(b_j\) 的第 \(i\) 位是 \(1\)，所以我们要遍历这些 \(j\)，如果 \(b_j\) 在第 \(i\) 位为 \(1\)，我们就要将 \(b_i\) 异或上 \(x\)。

  所以对于这种需要新插入 \(x\) 到线性基中的情况，我们只用做三步：

  1. 枚举 \(j<i\)，如果 \(x\) 在第 \(j\) 位上为 \(1\) 且 \(j\) 是已经存在于线性基中的主元，那么 \(x\) 异或上 \(b_j\)。
  2. 枚举 \(j>i\)，如果 \(b_j\) 在第 \(i\) 位上为 \(1\) 且 \(j\) 是已经存在于线性基中的主元，那么 \(b_j\) 异或上 \(x\)（注意这两步之间的顺序，为的就是此时用于异或的这个 \(x\) 已经是符合线性基要求的正确版本）。
  3. \(b_j\gets x\)，并且返回插入成功，结束。

如果一个 \(x\) 从始至终没有出现这样一个为 \(1\) 又还不是主元的二进制位 \(i\)，说明 \(x\) 和 \(B\) 是线性相关的，不需要插入 \(x\)。所以我们如果想判断一个 \(x\) 能否用当前的线性基凑出来，就可以参照插入的方式，如果插入失败并且最后遍历完所有二进制位之后的 \(x=0\)，那么说明 \(x\) 是能被 \(B\) 凑出来的。

其实你会发现上面整个过程就是相当于在做高斯消元。

我们将线性基的值域 \(|B|\) 看作 \(\log V\) 的（显然），那么每次插入的复杂度就是 \(\mathcal{O}(\log V)\) 的，因为至多只有一个位置我们会将其从自由元变为主元，而做一次这个过程是 \(\log V\) 的，遍历所有二进制位也是 \(\log V\) 的。

这里就出现一个问题，如果 \(x\) 其实包含了不止一个自由元位置，我们为什么只插入一次呢？我觉得也只需要插入一次，其他的仍然看作自由元是没有问题的。

给出插入 \(x\) 的代码实现：

auto insert(i64 x) {
   for (auto i = i64{50}; ~i; --i) {
      if (!((x >> i) & 1ll)) continue;
      if (b[i]) x ^= b[i];
      else {
         for (auto j = i64{0}; j < i; ++j)
            if ((x >> j) & 1ll) x ^= b[j];
         for (auto j = i + 1; j <= 50; ++j)
            if ((b[j] >> i) & 1ll) b[j] ^= x;
         b[i] = x;
         return 1; //insert success
      }
   }
   return 0; //insert failed
}

P3812：求解该数集的子集异或和最大值

因为一个线性基内部是线性无关的，并且 \(B\) 内的子集异或和能凑出 \(S\) 内的所有子集异或和，所以这相当于在问线性基内的子集异或和 \(\max\)。考虑到我们的线性基内主元的性质，每个主元位 \(i\) 在 \(B\) 中恰好出现一次，我们考虑将 \(B\) 中所有 \(B_i\) 异或起来即可。

auto getall() {
   auto ret = i64{0};
   for (auto i = 0; i <= 50; ++i) ret ^= b[i];
   return ret;
}

扩展地，考虑求 \(x\) 与该数集内一个子集的异或和最大值，直接遍历建好的基，如果 \(x\) 在第 \(i\) 位为 \(0\)，那么 \(x\gets x\oplus b_i\) 即可，正确性是类似的。

Loj #114：子集异或和第 \(k\) 大

首先容易发现，我们只把 \(b_i\ne0\) 的 \(b_i\) 放入 \(B\) 中，然后其实 \(B\) 中的子集异或和肯定互不相同。很好证，因为 \(B\) 内部是线性无关的，所以如果存在 \(b_x\oplus b_y=b_x'\oplus b_y'\Rightarrow b_x=b_x'\oplus b_y'\oplus b_y\)，矛盾了。所以如果凑不出 \(0\) 的话，总的不同异或和就有 \(2^{|B|}-1\) 个（能凑出 \(0\)，也就是 \(|B|<n\) 的情况，我们把 \(k\) 加上 \(1\) 就一样了）。然后就类似于我们把 \(B\) 中数看成不同的数位一样，将它们从大到小排序后，将 \(k\) 二进制拆分，假如 \(k\) 在第 \(i\) 位上为 \(1\)，将 \(ans\) 异或上 \(B_k\) 即可，完全可以类比把 \(B\) 中元素直接看作二进制数位的情况。复杂度 \(\mathcal{O}((n+q)\log V)\)。

类似的，可以利用上面的结论秒了P3857 [TJOI2008] 彩灯，直接统计方案数，答案就是 \(2^{|B|}\)，这里不用考虑能否凑出 \(0\) 是因为所有开关都不按（空集）就是 \(0\) 的情况。

Submission.

P4869：不去重的异或和排名

容易发现在线性基中的这 \(2^{|B|}\)（默认可以选择空集以达到 \(0\)）其实是把原本的 \(2^n\) 种情况去重后得来的（设原数集 \(S\) 中有 \(n\) 个元素），如果不去重直接问一个异或和在这 \(2^n\) 中方案中的排名呢？

很难发现一个结论，线性基中每种异或和，都满足它在原数集中有恰好 \(2^{n-|B|}\) 种子集可以异或出它。这是为什么？考虑我们先从 \(B\) 中选出一个数集 \(T\)，那么不同的 \(T\) 恰好对应了 \(S\) 内数的 \(2^{|B|}\) 种不同的异或和，由于线性基的性质，现在我们从不在线性基中的数集 \(S-B\) 中选出一个数集 \(T'\)（\(T'\) 可以为空，所以 \(T'\) 一共有 \(2^{n-|B|}\) 种选法），我们一定可以通过调整 \(T\) 是的 \(T\cup T'\) 异或出来的值与原先的 \(T\) 对应的异或值相同。这些调整方式和最后的 \(T\cup T'\) 固然是互不相同的，所以对于一个 \(T\)，它恰好对应了 \(2^{n-|B|}\) 种调整方式，即每种异或和对应 \(2^{n-|B|}\) 种选择子集的方式。

所以这题我们先求出 \(q\) 在线性基能得出的 \(2^{|B|}\) 种异或和中的排名（这可以通过将 \(B\) 拿出来然后排序，按照二进制分解的逆思路求出排名。注意我们直接二进制分解得出的排名是没有算上 \(0\) 的情况，所以实际排名 \(rk\) 还要加上 \(1\)），然后答案就是 \((rk-1)\times 2^{n-|B|}+1\)。

P4839：线性基合并

看起来好像线段树维护线性基合并诶！就是这个。合并 \(B_1,B_2\) 只需要把 \(B_2\) 中的元素依次插入到 \(B_1\) 中，然后在线段树上维护这个过程，在 \(x\) 插入 \(v\) 的时候将所有包含了 \(x\) 的区间的线性基都插入一个 \(v\) 就可以了（别维护 pushup，这很涨复杂度的）。总复杂度 \(\mathcal{O}(n\log n\log^2V)\)，1A 了捏！

P4151： 最大异或和路径

容易发现，答案的路径应该是由一条 \(1\to n\) 的简单路径以及一些连在上面的简单环组成的。

为什么可以忽视简单环到链上的这条路径呢？看图说话。异或的性质给了我骄傲的资本。于是相当于我们只需要求出所有的简单环，然后把它们扔进线性基，再查询 \(dis(1,n)\) 在该线性基中能异或出的最大值。

问题在于简单环可能有很多啊，我总不能一个个把它们全部找出来吧？（我认为暴力找环复杂度很错的说）经典做法是建出一棵生成树，然后选择 \(1\to n\) 的树上路径为基础链，那么发现我们只需要考虑只有一条非树边的简单环即可。为什么？容易发现其他更多非树边组成的简单环都能被这些环并出来，这就是异或的强大性质。

具体选生成树的话直接选 dfs 树就好了，这样要求 \(dis(x,y)\) 就可以在 dfs 原图的时候顺便做好了。最后对每条非树边 \((u,v,w)\)，得到一个简单环权值为 \(dis(x,y)\oplus w\)，扔进线性基查询 \(dis(1,n)\) 即可 （当时 WA 了好久是因为把异或写成或了）。

CF938G：带加边删边的异或和最短路

这里介绍离线套线段树分治的做法，多一个 \(\log n\) 但是比较无脑。

其实很类似于 P4151，但是要删除环不好做。发现没有强制在线，这时候很经典的思路就是只考虑有加边的情况，那么我们可以维护一个边带权并查集，在维护 \(fa_u\) 的同时维护 \(dis_u\) 表示 \(u\) 到 \(fa_u\) 的路径上的边权异或和，那么我们要求 \(dis(x,y)\) 就直接通过一直跳 \(fa\) 的方式，将 \(x,y\) 到根节点的 \(dis\) 异或起来就可以了。于是我们每次连边 \((u,v,w)\) 时，如果 \(u,v\) 目前还没有在同一个连通块内，那么连边 \(u,v\)，这里我采用的是按秩合并的并查集，并把 \(dis_{root(u)}=dis(u,v)\oplus w\)，这很好理解：

否则说明我们多出了一个环，这个环的非树边就是 \((u,v,w)\)，环长为 \(dis(u,v)\oplus w\)，这里 \(dis(u,v)\) 是 \(u,v\) 的树上距离。

那么把环扔到线性基里面就可以了。现在考虑上删边操作，直接套一个线段树分治，对每条边维护一个它出现的时间区间，然后由于不好撤销对线性基的操作，于是我们在最后遍历线段树维护询问的时候传参一个线性基，这样就只用管加边不用删了。复杂度我认为是 \(\mathcal{O}(q\log q\log V)\) 的。

Submission.

P3733：bitset 优化以及可“删除”的线性基

其实这题和上一个差不多，但是它有一个特殊的地方，就是它的 \(w\) 达到了 \(1000\) 位，这显然不能再用整数类型存储了，又因为是二进制表示所以其实每一位只有 \(01\)，故考虑 bitset 优化。用 bitset 维护线性基，单次插入查询复杂度变为 \(\mathcal{O}(\frac{len^2}{\omega})\)，其中 \(len\) 表示该线性基的长度。再套用一个线段树分治无脑做是 \(\mathcal{O}(q\log q \frac{len^2}{\omega})\)，又慢又丑。

考虑一种支持“删除”的线性基：我们维护一个不经消元的线性基，然后记录每个基内元素被删除的时刻，插入的时候我们也要给出该新元素被删除的时刻，然后我们贪心一下，在保证线性基性质的前提下使得基内的数被删除的时间最晚，于是我们就能写出如下的线性基，单次操作复杂度仍然是 \(\mathcal{O}(\frac{len^2}{\omega})\)：

namespace LinearBasis {
   std::array<std::bitset<M>, M> b;
   std::array<int, M> t; //每个基内元素被删除的时间

   auto init() {
      std::fill(ALL(t), -114514);
   }
   auto insert(std::bitset<M> x, int y)  {//插入一个在y时刻被删除的元素
      for (auto i = 1000; ~i; --i) {
         if (!x[i]) continue;
         if (y > t[i]) std::swap(x, b[i]), std::swap(y, t[i]);
         if (!y) return ;
         x ^= b[i];
      }
      return ;
   }
   auto query(int x) { //表示询问x时刻的答案
      std::bitset<M> ret; ret.reset();
      for (auto i = 1000; ~i; --i)
         if (t[i] > x && !ret[i]) ret ^= b[i];
      return ret;
   }

} //namespace LinearBasis

然后我们仍然采取离线，得出每一个环被加入、删除的时间，具体我们得出了每条边的加入删除时间后，按照加入时间做扫描线，将在当前时刻 \(t\) 加入的边全部加到并查集里面并相应地更新线性基中的环，加完后就能查询该时刻的答案了，注意一开始的 \(m\) 条边是不会被删掉的，重边自环其实不影响。时间复杂度 \(\mathcal{O}(q\frac{len^2}{\omega})\)，用这个做法去做 CF938G 就能做到 \(\mathcal{O}(q\log V)\)，很快的有没有。

Submission.

还有一种正宗的可删除线性基，它真的能支持在线的删除与修改基内元素（不过多一个 \(\log\)），只适用于 \(q,len\) 差不多规模的时候，这黑科技我没学会，可以参考 this。