线性基小记

command_block · 2020-10-21 15:10:04 · 个人记录

0.前置芝士

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

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

• 线性组合

  简单来说就是几个东西加权（数乘）之后加在一起。

• 线性有关/无关

  一组向量线性无关 \Leftrightarrow 没有向量可用有限个其他向量的线性组合所表示。

• 张成

  向量集合 V 的所有线性组合形成的集合 S 称作 V 的张成空间，记作 {\rm span}(V)

• 基

  若向量集合 B 线性无关，则称 B 是 {\rm span}(B) 的一组基。

  比如，三维空间可以以空间直角坐标系的三个轴（的方向向量）作为基。

  • 性质

  • 由 $B$ 线性无关，任意去掉一个向量，其余的都无法将其拼（线性组合）出来，显然也无法张成原来的 ${\rm span}(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,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 也必不成立。

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

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

若原有的 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

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

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

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

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

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

可以在 V-B 中选择一个子集 S ，S 中的每个向量都能被 B 拼出来，所以 S 的任意子集异或和都能被 B 拼出来。