线性基小记

command_block

2020-10-21 15:10:04

Personal

0.前置芝士

非必须知识，若对线性基已经比较熟悉，或有一定感性理解，可以选择性跳过。

和线性代数有关。目前还比较简略，建议配合其他资料食用。

1.\rm OI 中的线性基

在 \rm OI 中，“线性基” 专用于解决有关异或的一些问题。

异或运算可以看做 \bmod\ 2 意义下的向量加法。

类似地，我们定义 {\rm span}(S) 为数字集合 S 的所有子集的异或和组成的集合。

方便起见，设本文中涉及的二进制数位长为 k ，且不超过计算机位长 w。

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

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 加入线性基。过程结束。

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。

也有另外一种做法，首先将三角基进一步消成对角基，然后直接输出所有元素的异或和即可。

原理和上面的按位贪心是类似的，只不过第二种情况不会出现。

若原有的 V 本就是线性无关的，则异或不到 0 ，能得到的异或值也就只有 2^{|B|}-1 个。（有时允许选空集则无需考虑这种情况）

反之，能得到 0 ，则为 2^{|B|} 个。

附 : 利用这个小结论即可做掉 P3857 [TJOI2008]彩灯。

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

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

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

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

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

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

例题 :

  1. P3292 [SCOI2016]幸运数字

  2. P4839 P哥的桶

  3. P5607 [Ynoi2013]无力回天NOI2017

题意 ： 将一个集合 V 的所有子集异或和排序（不去重），问某个数的排名。

若去重，则不难转化成前面的 k 小异或和问题。

结论 : 有 2^{|B|} 种异或值，每个异或和都出现次数相同，为 2^{|V|-|B|}。

证明 ：首先选出 B 的一个子集异或值 s，考虑拼出 s 的方案数。

可以在 V-B 中选择一个子集 S ，S 中的每个向量都能被 B 拼出来，所以 S 的任意子集异或和都能被 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]$ 的线性基。