线性基

回想高中数学立体几何中基向量的概念，我们可以在三维欧氏空间中找到一组基向量 $i$ ， $j$ ， $k$ ，之后空间中任意一个向量都可以由这组基向量表示。换句话说，我们可以 通过有限的基向量来描述无限的三维空间，这足以体现基向量的重要性。

三维欧氏空间是特殊的线性空间，三维欧氏空间的基向量在线性空间中就被推广为了线性基。

OI 中有关线性基的应用一般只涉及两类线性空间： $n$ 维实线性空间 $R^{n}$ 和 $n$ 维布尔域线性空间 $Z_{2}^{n}$ ，我们会在应用一节中详细介绍。若您不熟悉线性代数，则推荐从应用部分开始阅读。

以下会从一般的线性空间出发来介绍线性基，并给出线性基的常见性质。

前置知识：线性空间。

线性基是线性空间的一组基，是研究线性空间的重要工具。

定义

称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组 Hamel 基 或 线性基，简称基。

规定线性空间 ${θ}$ 的基为空集。

可以证明任意线性空间均存在线性基¹，我们定义线性空间 $V$ 的维数为线性基的元素个数（或势），记作 $\dim V$ 。

性质

对于有限维线性空间 $V$ , 设其维数为 $n$ , 则：
1. $V$ 中的任意 $n + 1$ 个向量线性相关。
2. $V$ 中的任意 $n$ 个线性无关的向量均为 $V$ 的基。
3. 若 $V$ 中的任意向量均可被向量组 $a_{1}, a_{2}, \dots, a_{n}$ 线性表出，则其是 $V$ 的一个基。
  
  证明
  
  任取 $V$ 中的一组基 $b_{1}, b_{2}, \dots, b_{n}$ , 由已知条件，向量组 $b_{1}, b_{2}, \dots, b_{n}$ 可被 $a_{1}, a_{2}, \dots, a_{n}$ 线性表出，故
  $n = rank {b_{1}, b_{2}, \dots, b_{n}} \leq rank {a_{1}, a_{2}, \dots, a_{n}} \leq n$
  因此 $rank {a_{1}, a_{2}, \dots, a_{n}} = n$
4. $V$ 中任意线性无关向量组 $a_{1}, a_{2}, \dots, a_{m}$ 均可通过插入一些向量使得其变为 $V$ 的一个基。
（子空间维数公式）令 $V_{1}, V_{2}$ 是关于 $P$ 的有限维线性空间，且 $V_{1} + V_{2}$ 和 $V_{1} \cap V_{2}$ 也是有限维的，则 $\dim V_{1} + \dim V_{2} = \dim (V_{1} + V_{2}) + \dim (V_{1} \cap V_{2})$

证明

设 $\dim V_{1} = n_{1}$ , $\dim V_{2} = n_{2}$ , $\dim (V_{1} \cap V_{2}) = m$ .

取 $V_{1} \cap V_{2}$ 的一组基 $a_{1}, a_{2}, \dots, a_{m}$ , 将其分别扩充为 $V_{1}$ 和 $V_{2}$ 中的基： $a_{1}, a_{2}, \dots, a_{m}, b_{1}, b_{2}, \dots, b_{n_{1} - m}$ 和 $a_{1}, a_{2}, \dots, a_{m}, c_{1}, c_{2}, \dots, c_{n_{2} - m}$ .

接下来只需证明向量组 $a_{1}, a_{2}, \dots, a_{m}, b_{1}, b_{2}, \dots, b_{n_{1} - m}, c_{1}, c_{2}, \dots, c_{n_{2} - m}$ 线性无关即可。

设 $\sum_{i = 1}^{m} r_{i} a_{i} + \sum_{i = 1}^{n_{1} - m} s_{i} b_{i} + \sum_{i = 1}^{n_{2} - m} t_{i} c_{i} = θ$ .

则 $\sum_{i = 1}^{n_{2} - m} t_{i} c_{i} = - \sum_{i = 1}^{m} r_{i} a_{i} - \sum_{i = 1}^{n_{1} - m} s_{i} b_{i}$ .

注意到上式左边在 $V_{2}$ 中，右边在 $V_{1}$ 中，故两边均在 $V_{1} \cap V_{2}$ 中，因此 $\sum_{i = 1}^{n_{2} - m} t_{i} c_{i} = \sum_{i = 1}^{m} k_{i} a_{i}$

故 $t_{1} = t_{2} = \dots = t_{n_{2} - m} = k_{1} = k_{2} = \dots = k_{m} = 0$ , 进而 $r_{1} = r_{2} = \dots = r_{m} = s_{1} = s_{2} = \dots = s_{n_{1} - m} = t_{1} = t_{2} = \dots = t_{n_{2} - m} = 0$
令 $V_{1}, V_{2}$ 是关于 $P$ 的有限维线性空间，且 $V_{1} + V_{2}$ 和 $V_{1} \cap V_{2}$ 也是有限维的，则下列诸款等价：
1. $V_{1} + V_{2} = V_{1} \oplus V_{2}$ .
2. $\dim V_{1} + \dim V_{2} = \dim (V_{1} + V_{2})$ .
3. 若 $a_{1}, a_{2}, \dots, a_{n}$ 是 $V_{1}$ 的一组基， $b_{1}, b_{2}, \dots, b_{m}$ 是 $V_{2}$ 的一组基，则 $a_{1}, a_{2}, \dots, a_{n}, b_{1}, b_{2}, \dots, b_{m}$ 是 $V_{1} + V_{2}$ 的一组基。
Note

1,3 两条可推广到无限维线性空间中

例子

考虑 $R^{2}$ 的基。

如图

$u, v$ 是一组基。
如图

$u, v$ 是一组基。
如图

$u, v$ 不是一组基，因为 $u = - v$ .
如图

$u, v, w$ 不是一组基，因为 $u + 4 v + 6 w = θ$ .

正交基与单位正交基

若线性空间 $V$ 的一组基 $B$ 满足 $\forall b, b^{'} \in B, (b, b^{'}) \neq 0 ⟺ b = b^{'}$ （即两两正交），则称这组基是 正交基。

若线性空间 $V$ 的一组正交基 $B$ 还满足 $\forall b \in B, | b | = \sqrt{(b, b)} = 1$ ，则称这组基是 单位正交基。

任意有限维线性空间 $V$ 的基都可以通过 Schmidt 正交化变换为正交基。

应用

根据前文内容，我们可以利用线性基实现：

求给定向量组的秩；
对给定的向量组，找到一组极大线性无关组（或其张成的线性空间的一组基）；
向给定的向量组插入某些向量，在插入操作后的向量组中找到一组极大线性无关组（或其张成的线性空间的一组基）；
对找到的一组极大线性无关组（或基），判断某向量能否被其线性表出；
对找到的一组极大线性无关组（或基），求其张成的线性空间中的特殊元素（如最大元、最小元等）。

在 OI 中，我们一般将 $n$ 维实线性空间 $R^{n}$ 下的线性基称为 实数线性基， $n$ 维布尔域线性空间 $Z_{2}^{n}$ 下的线性基称为 异或线性基。

Tip

$Z_{2}$ 中的加法为异或，乘法为与，可以证明 $Z_{2}$ 是域。

可以证明代数系统 $(Z_{2}^{n}, +, \cdot, Z_{2})$ 是线性空间，其中：

(a_{1}, \dots, a_{n}) + (b_{1}, \dots, b_{n}) := (a_{1} + b_{1}, \dots, a_{n} + b_{n}),

k \cdot (a_{1}, \dots, a_{n}) := (k a_{1}, \dots, k a_{n}) .

即加法是异或，数乘是与。

以异或线性基为例，我们可以根据给定的一组布尔序列 ${x_{1}, \dots, x_{m}}$ 构造出一组异或线性基 $B = {b_{1}, \dots, b_{n}}$ ，这组基有如下性质：

$B$ 中任意非空子集的异或和不为 $0$ ；
对 $X$ 中的任意元素 $x$ ，都可在 $B$ 中取出若干元素使其异或和为 $x$ ；
对任意满足上两条的集合 $B^{'}$ ，其元素个数不会小于 $B$ 的元素个数。

我们可以利用异或线性基实现：

判断一个数能否表示成某数集子集的异或和；
求一个数表示成某数集子集异或和的方案数；
求某数集子集的最大/最小/第 $k$ 大/第 $k$ 小异或和；
求一个数在某数集子集异或和中的排名。

构造方法

因为异或线性基与实数线性基没有本质差别，所以接下来以异或线性基为例，实数线性基版本的代码只需做一点简单修改即可。

贪心法

对原集合的每个数 $p$ 转为二进制，从高位向低位扫，对于第 $x$ 位是 $1$ 的，如果 $a_{x}$ 不存在，那么令 $a_{x} \leftarrow p$ 并结束扫描，如果存在，令 $p \leftarrow p xor a_{x}$ 。

查询原集合内任意几个元素 $xor$ 的最大值，只需将线性基从高位向低位扫，若 $xor$ 上当前扫到的 $a_{x}$ 答案变大，就把答案异或上 $a_{x}$ 。

为什么能行呢？因为从高往低位扫，若当前扫到第 $i$ 位，意味着可以保证答案的第 $i$ 位为 $1$ ，且后面没有机会改变第 $i$ 位。

查询原集合内任意几个元素 $xor$ 的最小值，就是线性基集合所有元素中最小的那个。

查询某个数是否能被异或出来，类似于插入，如果最后插入的数 $p$ 被异或成了 $0$ ，则能被异或出来。

代码（洛谷 P3812 【模板】线性基）

#include <algorithm>
#include <iostream>
using ull = unsigned long long;

ull p[64];

void insert(ull x) {
  for (int i = 63; ~i; --i) {
    if (!(x >> i))  // x 的第 i 位是 0
      continue;
    if (!p[i]) {
      p[i] = x;
      break;
    }
    x ^= p[i];
  }
}

using std::cin;
using std::cout;

int main() {
  int n;
  cin >> n;
  ull a;
  for (int i = 1; i <= n; ++i) {
    cin >> a;
    insert(a);
  }
  ull ans = 0;
  for (int i = 63; ~i; --i) {
    ans = std::max(ans, ans ^ p[i]);
  }
  cout << ans << '\n';
  return 0;
}

高斯消元法

高斯消元法相当于从线性方程组的角度去构造线性基，正确性显然。

代码（洛谷 P3812 【模板】线性基）

#include <iostream>
using ull = unsigned long long;
constexpr int MAXN = 1e5 + 5;

ull deg(ull num, int deg) { return num & (1ull << deg); }

ull a[MAXN];
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int row = 1;
  for (int col = 63; ~col && row <= n; --col) {
    for (int i = row; i <= n; ++i) {
      if (deg(a[i], col)) {
        std::swap(a[row], a[i]);
        break;
      }
    }
    if (!deg(a[row], col)) continue;
    for (int i = 1; i <= n; ++i) {
      if (i == row) continue;
      if (deg(a[i], col)) {
        a[i] ^= a[row];
      }
    }
    ++row;
  }
  ull ans = 0;
  for (int i = 1; i < row; ++i) {
    ans ^= a[i];
  }
  cout << ans << '\n';
  return 0;
}

性质

贪心法构造的线性基具有如下性质：

线性基没有异或和为 $0$ 的子集。
线性基中各数二进制最高位不同。

高斯消元法构造出的线性基满足如下性质：

高斯消元后的矩阵是一个行简化阶梯形矩阵。

该性质包含了贪心法构造的线性基满足的两条性质

如果不理解这条性质的正确性，可以跳转高斯消元。

提供一组样例：

5
633 211 169 841 1008

二进制表示：

贪心法生成的线性基：

高斯消元法生成的线性基：

这是一条非常好的性质，能帮我们更方便的解决很多问题。比如：给定一些数，选其中一些异或起来，求异或最大值，如果用贪心法构造线性基，需要再做一遍贪心，如果 ans 的当前位是 0，那么异或一定会更优，否则当前位如果为 1，则一定不会更优；而使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。

对于其他比较经典的问题（查询一个数能否被异或得到，查询能被异或得到的第 $k$ 大数等），高斯消元法得到的线性基也能更加方便地解决。

时间复杂度

设向量长度为 $n$ , 总数为 $m$ , 则时间复杂度为 $O (n m)$ . 其中高斯消元法的常数略大。

若是实数线性基，则时间复杂度为 $O (n^{2} m)$ .

线性基合并

线性基的合并只需要暴力处理，即将要合并的一组线性基暴力地插入到另一组线性基即可。单次合并的时间复杂度是 $O (n^{2})$ （异或线性基）或 $O (n^{3})$ （实数线性基）。

线性基求交

线性基求交，严格地说就是求它们张成的两个线性空间的交空间的一组线性基。本节介绍两种算法。这两种算法，单次求交的时间复杂度都是 $O (n^{2})$ （异或线性基）或 $O (n^{3})$ （实数线性基）。

朴素算法

设要求交的线性基分别是 $α$ 和 $β$ 。线性基求交的算法只需要对线性基暴力合并的算法做如下调整：（以异或线性基为例）

将线性基 $β$ 中的向量 $β_{j}$ 利用贪心法尝试插入到 $α$ 中，并初始化线性基的交 $γ$ 为空集；
在插入时，需要记录要插入的向量中，线性基 $β$ 中元素的贡献。具体地，维持一个新向量 $b$ ，初始化为 $β_{j}$ ，而且，如果正在插入的向量与线性基中第 $x$ 位的向量取了异或，那么贡献 $b$ 也要与第 $x$ 位记录的贡献 $b_{x}$ 取一次异或；
如果插入成功，在线性基的第 $x$ 位插入了向量 $β_{j}^{'}$ ，就将第 $x$ 位记录的 $b_{x}$ 改为得到 $β_{j}^{'}$ 的过程中线性基 $β$ 中元素的贡献 $b$ ；
如果插入不成功，就将过程中记录到的线性基 $β$ 中元素的贡献 $b$ 插入到 $γ$ 中。

这样得到的线性基 $γ$ 就是所求的交，当然，该算法同时也求出了线性基的并。

对算法的解释

设合并后的线性基为 ${α_{1}, \dots, α_{m}, β_{j_{1}}^{'}, \dots, β_{j_{ℓ}}^{'}}$ ，其中， $β_{j_{k}}^{'}$ 是插入 $β_{j_{k}}$ 时最后得到的向量。那么， ${α_{1}, \dots, α_{m}, β_{j_{1}}, \dots, β_{j_{ℓ}}}$ 同样是一组合并后的线性基。记 $β^{+}$ 为集合 ${β_{j_{1}}, \dots, β_{j_{ℓ}}}$ ，则合并后的基可以写作 $α \cup β^{+}$ 。而且，和空间中的每个向量 $c$ 都可以唯一地表示成

c = a \oplus b

的形式，其中， $a \in span α$ 且 $b \in span β^{+}$ 。这个分解中的 $b$ 就是前文算法所试图记录的「线性基 $β$ 中元素的贡献」。严格地说，只是 $β$ 中最后成功插入的那些向量的贡献。

对于成功的插入，最后记录的 $b$ 就是该分解中的 $b$ 项。设 $β_{j} \in β^{+}$ 。初始时， $β_{j} = 0 \oplus β_{j}$ ，已经是 $β_{j}$ 在基 $α \cup β^{+}$ 上的正确的分解。在更新 $β_{j}^{'} = a \oplus b$ 为 $β_{j}^{'} \oplus c_{x}$ 时，因为 $β_{j}^{'} \oplus c_{x} = (a \oplus a_{x}) \oplus (b \oplus b_{x})$ ，所以，只需要更新 $b$ 为 $b \oplus b_{x}$ ，就可以保证分解依然正确。因此，归纳可知，最后插入 $β_{j}^{'}$ 到合并后的线性基中时，记录的贡献 $b$ 就是上述分解中的 $b$ 项。

对于不成功的插入，最后要插入的变量一定会变成 $0$ ，而此时的贡献 $b$ 要插入到 $γ$ 中。此时，如果重复上面的论证，会发现仍然能够保证在插入过程中总是有 $β_{j}^{'} = a \oplus b$ ，且 $a \in span α$ ，只是 $b$ 不再属于 $span β^{+}$ 。这是因为初始化时， $β_{j} = 0 \oplus β_{j}$ 中的 $β_{j} \notin β^{+}$ 。除此之外，贡献更新时异或的项都属于 $span β^{+}$ 。所以，实际上，有 $b \oplus β_{j} \in span β^{+}$ 。

那么，为什么将这些插入不成功时的 $b$ 都插入到 $γ$ 中，就能得到交空间的线性基呢？首先，插入 $β_{j}$ 不成功，最后一定会得到 $0 = a \oplus b$ ，其中， $a \in span α$ 且 $b \in span (β^{+} \cup {β_{j}}) \subseteq span β$ 。因此， $b = a$ 必然位于交空间 $span α \cap span β$ 中。反过来，设 $c$ 是交空间中的任意元素，因为 $c \in span β$ ，所以 $c$ 可以表示为 $β$ 中元素的线性组合（异或和）：

c = ⨁_{β_{j} \in β} λ_{j} β_{j},

其中， $λ_{j} \in {0, 1}$ 。对于每一个 $β_{j} \notin β^{+}$ ，记相应的插入到 $γ$ 中的贡献为 $b_{j}$ ，就有

c \oplus ⨁_{β_{j} \notin β^{+}} λ_{j} b_{j} = ⨁_{β_{j} \in β^{+}} λ_{j} β_{j} + ⨁_{β_{j} \notin β^{+}} λ_{j} (β_{j} \oplus b_{j}),

注意到， $b_{j}$ 和 $c$ 都位于交空间中，因而左侧必然也位于交空间中，故而左侧可以写成 $α$ 中元素的线性组合；同时，右侧所有项，要么 $β_{j} \in β^{+}$ ，要么 $β_{j} \notin β^{+}$ 且 $β_{j} \oplus b_{j} \in β^{+}$ ，故而，右侧实际上是 $β^{+}$ 中元素的线性组合。但是， $α \cup β^{+}$ 线性无关，故而所有的系数都是 $0$ ，也就是说 $c = ⨁_{β_{j} \notin β^{+}} λ_{j} b_{j} \in span {b_{1}, \dots, b_{j}}$ 。这就说明了，这些无法插入的向量的贡献 $b$ 共同张成了交空间。

根据这一解释，过程中维护贡献 $b$ 的目的，实际上是为了维护分解 $a \oplus b$ ；而且，最后向 $γ$ 插入贡献时也总有 $a = b$ 。所以，无论维护 $α$ 还是 $β$ 中元素的贡献（即无论维护 $a$ 还是 $b$ ），得到的结果都是正确的。如果要维护线性基 $α$ 中元素的贡献，只需要修改初始化时相应贡献的取值：每个 $α$ 中的向量 $α_{i}$ 初始就有贡献 $α_{i}$ ，而插入的 $β_{j}$ 初始贡献为 $0$ 。

模板题代码如下：

代码（Library Checker Intersection of

F_{2}

vector spaces）

#include <array>
#include <iostream>

class LinearBasis {
  static constexpr int K = 30;
  std::array<int, K> a;

  // Size of basis.
  int size() const {
    int res = 0;
    for (auto x : a) {
      if (x) {
        ++res;
      }
    }
    return res;
  }

 public:
  LinearBasis() : a{} {}

  // Insert vector x.
  void insert(int x) {
    for (int k = K - 1; ~k && x; --k) {
      if ((x >> k) & 1) {
        if (!a[k]) {
          a[k] = x;
        }
        x ^= a[k];
      }
    }
  }

  // Return a basis for *THIS intersecting RHS.
  LinearBasis intersect(const LinearBasis& rhs) const {
    LinearBasis res;
    std::array<int, K> c = a, b_parts = {};
    for (int i = K - 1; ~i; --i) {
      int x = rhs.a[i], b_part = x;
      for (int k = i; ~k && x; --k) {
        if ((x >> k) & 1) {
          if (!c[k]) {
            c[k] = x;
            b_parts[k] = b_part;
          }
          x ^= c[k];
          b_part ^= b_parts[k];
        }
      }
      res.insert(b_part);
    }
    return res;
  }

  // Output.
  void print() const {
    std::cout << size();
    for (auto x : a) {
      if (x) {
        std::cout << ' ' << x;
      }
    }
    std::cout << '\n';
  }
};

int main() {
  int t;
  std::cin >> t;
  for (; t; --t) {
    LinearBasis a, b;
    int n;
    std::cin >> n;
    for (; n; --n) {
      int x;
      std::cin >> x;
      a.insert(x);
    }
    int m;
    std::cin >> m;
    for (; m; --m) {
      int x;
      std::cin >> x;
      b.insert(x);
    }
    a.intersect(b).print();
  }
  return 0;
}

Zassenhaus 算法

另一种等价的做法是 Zassenhaus 算法，它同样可以同时计算出两个线性基的并和交。复杂度和上文完全一致。

具体步骤如下：

初始化一个向量长度为 $2 n$ 的线性基 $γ$ 为空，其中的向量写成 $(a, b)$ 的形式，且 $a$ 和 $b$ 长度均为 $n$ ；
将 $α$ 中的元素 $α_{i}$ 以 $(α_{i}, α_{i})$ 的形式插入 $γ$ 中；
将 $β$ 中的元素 $β_{j}$ 以 $(β_{j}, 0)$ 的形式插入 $γ$ 中；
最后得到的线性基 $γ$ 中的所有非零元素 $(c_{k}, d_{k})$ 中， $c_{k}$ 非零的那些向量中项 $c_{k}$ 的全体组成了 $α$ 和 $β$ 的并的线性基， $c_{k}$ 为零的那些向量中项 $d_{k}$ 的全体组成了 $α$ 和 $β$ 的交的线性基。

算法中的构造线性基的方法可以是贪心法或高斯消元法，只要保证 $γ$ 中的线性基组成行阶梯型矩阵即可。

将 Zassenhaus 算法中的消元的步骤与上面的朴素算法相比较，很容易发现，基于贪心法的 Zassenhaus 算法相当于维护 $α$ 中元素的贡献的朴素算法。如果转而先插入所有 $(α_{i}, 0)$ ，再插入所有 $(β_{j}, β_{j})$ ，那么基于贪心法的 Zassenhaus 算法就相当于维护 $β$ 中元素贡献的朴素算法。根据消元步骤的等价性，Zassenhaus 算法的正确性也是成立的。

除此之外，还可以再提供一个独立且更为一般的代数证明：

正确性证明

设 $V$ 为一线性空间，且有子空间 $U = span α$ 和 $W = span β$ 。算法本身相当于通过化简为行阶梯型来求子空间

H = span ({(α_{i}, α_{i}) : α_{i} \in α} \cup {(β_{j}, 0) : β_{j} \in β})

的一组基 $γ$ 。算法最后， $γ$ 中的元素 $(c_{k}, d_{k})$ 根据 $c_{k} \neq 0$ 与否需要分为两类，所以不妨考察投影映射 $π : H \to V$ 且 $π (a, b) = a$ 。于是， $π (H) = U + W$ 且容易验证

\begin{aligned} \ker π & = H \cap ({0} \times V) = {0} \times (U \times W) . \end{aligned}

根据线性映射的相关定理，有 $\dim H = \dim π (H) + \dim \ker π = \dim (U + W) + \dim (U \cap W)$ 。

行阶梯型矩阵的前几列仍然是行阶梯型矩阵，因而 $c_{k} \neq 0$ 的行的数目，恰好等于 $α \cup β$ 的行秩，亦即 $\dim (U + W)$ ；而且，这些行中 $c_{k}$ 的集合就形成了 $U + W$ 的一组基。剩下的非零行恰好有 $\dim (U \cap W)$ 个，且都满足 $c_{k} = 0$ 。对于这些行中的 $d_{k}$ ，因为有 $(0, d_{k}) \in \ker π$ ，所以 $d_{k} \in U \cap W$ ；而且， $(0, d_{k})$ 作为行阶梯型矩阵的行，必然线性无关，这就说明这些 $d_{k}$ 都线性无关。综合起来，这些 $d_{k}$ 是交空间 $U \cap W$ 中大小为 $\dim (U \cap W)$ 的线性无关组，所以也必然是该空间的一组基。

模板题代码如下：

代码（Library Checker Intersection of

F_{2}

vector spaces）

#include <iostream>
#include <vector>

class LinearBasis {
  int K;
  std::vector<long long> a;

 public:
  LinearBasis(int K) : K(K), a(K) {}

  // Insert vector x.
  void insert(long long x) {
    for (int k = K - 1; ~k && x; --k) {
      if ((x >> k) & 1) {
        if (!a[k]) {
          a[k] = x;
        }
        x ^= a[k];
      }
    }
  }

  // Output those not exceeding 2^k.
  void print(int k) const {
    int sz = 0;
    for (int i = 0; i < k; ++i) {
      if (a[i]) {
        ++sz;
      }
    }
    std::cout << sz;
    for (int i = 0; i < k; ++i) {
      if (a[i]) {
        std::cout << ' ' << a[i];
      }
    }
    std::cout << '\n';
  }
};

int main() {
  constexpr int K = 30;
  int t;
  std::cin >> t;
  for (; t; --t) {
    LinearBasis c(K << 1);
    int n;
    std::cin >> n;
    for (; n; --n) {
      int x;
      std::cin >> x;
      c.insert(((long long)x << K) | x);
    }
    int m;
    std::cin >> m;
    for (; m; --m) {
      int x;
      std::cin >> x;
      c.insert((long long)x << K);
    }
    c.print(K);
  }
  return 0;
}

注意，输出时只需要考虑前 $n$ 位均为零的向量即可。

拓展：前缀线性基

本节只讨论异或线性基的情形，并假设单个向量可以存储在 $O (1)$ 的空间内，且单次操作复杂度总是 $O (1)$ 的。

对于需要多次查询区间异或最大值的情形，一种常见的做法是猫树配合线性基，时间复杂度为 $O (n m \log m + n^{2} q)$ ，其中， $n$ 是向量长度， $m$ 是序列长度， $q$ 是询问次数。另一种可行的做法是利用前缀线性基（或称时间戳线性基），可以将复杂度降低到 $O (n (m + q))$ 。

前缀线性基允许对于序列的每个前缀，都维护该前缀的所有后缀的线性基，这样就可以支持查询每个区间的线性基。注意到序列的某个前缀 $[1, i]$ 的所有后缀 $[j, i]$ 的线性基是相互包含的，即 $[j, i]$ 的线性基总是包含着 $[j + 1, i]$ 的线性基，所以，这些后缀的线性基中互不相同的至多只有 $n$ 种，而且总是可以通过向空集中逐步添加新的向量来得到自 $[i, i]$ 到 $[1, i]$ 所有这些后缀的线性基。因此，利用这个单调性，只需要为添加的每个向量 $v$ ，都标记它出现的最大下标 $t$ ，就可以在 $O (n)$ 的空间内存储所有后缀的线性基。而且，查询区间 $[j, i]$ 对应的线性基时，只需要在 $i$ 处的前缀线性基中仅保留标记 $t \geq j$ 的那些向量即可。

不妨将每个向量 $v$ 的标记 $t$ 称为它的时间戳。线性基中的向量 $v$ 总是可以表示为原序列中某些元素的异或和，比如 $v_{i_{1}} \oplus v_{i_{2}} \oplus \dots \oplus v_{i_{k}}$ 。而在所有这样的可能的表示中，最小下标的最大值就是 $t$ ，即

t (v) = max {j : \exists i_{1}, \dots, i_{k} \in [j, i] s.t. v = v_{i_{1}} \oplus v_{i_{2}} \oplus \dots \oplus v_{i_{k}}} .

这个表达式不过是将上一段的叙述用形式的语言写出来而已。它给我们带来的启发是，要维护线性基中每个向量 $v$ 的时间戳，只需要贪心地选取尽可能新的向量替换掉旧的向量即可。

基于上文提到的贪心法构造线性基，前缀线性基在构造过程中做了如下调整：

为线性基中保留的每个向量 $a_{x}$ 都保存一个时间戳 $t_{x}$ ，初始时均设为 $0$ ；
要添加序列中第 $i$ 个向量 $v$ ，仍然从高位向低位扫，但同时需要记录当前时间 $i$ ；
如果 $v$ 的第 $x$ 位是一，就比较线性基中已有的向量 $a_{x}$ 的时间戳 $t_{x}$ 和当前时间 $i$ ：
- 如果 $i > t_{x}$ ，即要添加的向量时间更晚，就将 $a_{x}$ 设为 $v$ ，并更新时间戳为 $i$ ，并将旧的 $a_{x}$ 异或 $v$ 的结果 $a_{x} \oplus v$ 按照之前记录的时间 $t_{x}$ 继续添加过程；
- 如果 $i < t_{x}$ ，即要添加的向量时间更早，不更新 $a_{x}$ 和 $t_{x}$ ，将 $v$ 异或 $a_{x}$ 后继续添加即可。

也就是说，如果当前位可以通过较新的向量表示，就直接用较新的向量；否则，保留原来的向量。在更新位置 $x$ 的向量时，不能将异或的结果 $a_{x} \oplus v$ 存入位置 $x$ ，因为异或的结果 $a_{x} \oplus v$ 的时间戳为 $min {t (a_{x}) = t (v)} = t (a_{x})$ ，小于要添加的变量 $v$ 的时间戳 $t (v)$ 。同样的原因，高斯消元法构造线性基的过程中向上更新时可能会破坏时间戳的性质，所以不再适用于构造前缀线性基。

模板题代码如下：

代码（Codeforces 1100F Ivan and Burgers）

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <vector>

class LinearBasis {
  static constexpr int K = 20;
  std::array<int, K> a, t;

 public:
  LinearBasis() : a{}, t{} {}

  // Insert vector x at time i.
  void insert(int x, int i) {
    for (int k = K - 1; ~k && x; --k) {
      if (((x >> k) & 1)) {
        if (i > t[k]) {
          std::swap(a[k], x);
          std::swap(t[k], i);
        }
        x ^= a[k];
      }
    }
  }

  // Find max xor of subsets of elements from time i till now.
  int query(int i) const {
    int res = 0;
    for (int k = K - 1; ~k; --k) {
      if (t[k] >= i && (res ^ a[k]) > res) {
        res ^= a[k];
      }
    }
    return res;
  }
};

int main() {
  int n;
  std::cin >> n;
  std::vector<int> c(n + 1);
  for (int i = 1; i <= n; ++i) std::cin >> c[i];
  int q;
  std::cin >> q;
  std::vector<std::array<int, 2>> qu(q);
  for (auto& v : qu) std::cin >> v[0] >> v[1];
  std::vector<int> ids(q);
  std::iota(ids.begin(), ids.end(), 0);
  std::sort(ids.begin(), ids.end(),
            [&](int l, int r) -> bool { return qu[l][1] < qu[r][1]; });
  LinearBasis lb;
  std::vector<int> res(q);
  for (int i = 1, j = 0; i <= n; ++i) {
    lb.insert(c[i], i);
    for (; j < q && qu[ids[j]][1] == i; ++j) {
      res[ids[j]] = lb.query(qu[ids[j]][0]);
    }
  }
  for (int x : res) std::cout << x << '\n';
  return 0;
}

如果需要在线询问，也可以用 $O (m n)$ 的空间将每个前缀处的前缀线性基都存下来再查询，这可以看作是一种「可持久化」线性基。如果需要用到高斯消元法得到的线性基的性质，可以在查询时另行处理。

练习题

参考资料与注释

Proof that every vector space has a basis ↩

本页面最近更新：2025/5/24 12:24:08，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Ir1d, MegaOwIer, c-forrest, Enter-tainer, Great-designer, cesonic, ksyx, lychees, RUIN-RISE, wjy-yy, aofall, CoelacanthusHex, iamtwz, Marcythm, Menci, ouuan, Persdre, rsdbkhusky, shuzhouliu, Xeonacid, yusancky
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用