G61【模板】线性基 高斯消元法 P3812 最大异或和 G64【模板】线性基 贪心法 P3812 最大异或和

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
LL p[64];
void ins(LL v) 
{
    for (int i = 63; i >= 0; i--) if ((v >> i) & 1) // v 的第 i 位是 1
    { 
        if (p[i] == 0) { p[i] = v; break; } 
        else v ^= p[i];
    }
}

int main() 
{
    int n; scanf("%d", &n);
    LL v; memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; ++i) 
    {
        scanf("%llu", &v);
        ins(v);
    }
    LL ans = 0;
    for (int i = 63; i >= 0; i--) ans = max(ans, ans ^ p[i]);
    printf("%llu\n", ans);
    return 0;
}

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

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

例题 :

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$ 拼出来。

$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]$ 的线性基。