给 $n$ 个数，从中任选一些异或起来，最大能得到多少？$n = 50$ 时子集有 $2^{50}$ 个，枚举不动。可是这些子集的异或值里有大量重复：$a$、$b$、$a \oplus b$ 三个数，任选子集能得到的值和只用 $a$、$b$ 时一模一样，第三个数是多余的。把多余的数一个个去掉，剩下的数最多 60 个（每个数 60 位），能异或出的值却一个不少。剩下的这组数就是线性基。要说清楚“多余”是什么意思、为什么最多剩 60 个，需要把异或放进线性代数里看。
1. 异或就是模 2 加法
1.1 一个数是 GF(2) 上的向量
把一个小于 $2^{60}$ 的数写成 60 位二进制，每一位是 0 或 1，这个数就成了一个 60 维向量。两个数异或是逐位相加再模 2：$1 \oplus 1 = 0$ 正好是 $1 + 1 \equiv 0 \pmod 2$。只有 0、1 两个元素，加法和乘法都模 2 的域记作 GF(2)（也写 $\mathbb{F}_2$），所以异或就是 GF(2) 上的向量加法。
GF(2) 里系数只有 0 和 1，一个线性组合 $x_1 a_1 + x_2 a_2 + \cdots + x_n a_n$（$x_i \in \{0, 1\}$）就是“把 $x_i = 1$ 的那些数异或起来”。子集异或和与线性组合是同一件事，线性代数的几个概念可以直接搬过来：
- 张成的空间：所有子集异或和组成的集合，记作 $\operatorname{span}(a_1, \dots, a_n)$。
- 线性无关：没有一个非空子集的异或和等于 0。题面写“不存在异或和为 0 的非空子集”，说的就是线性无关。
- 基与秩：一组线性无关、又能异或出空间里每个值的数叫这个空间的一组基；基里数的个数是空间的维数，也叫原来那组数的秩，记作 $r$。60 维空间里线性无关的数最多 60 个，所以 $r \le 60$。
开头说的“多余”就是“能被别的数异或出来”，去掉它不改变张成的空间；去到不能再去时，剩下的数线性无关，就是一组基。换成基以后，能异或出的值不变，数的个数从 $n$ 降到 $r \le 60$，后面所有问题都在这至多 60 个数上做。
1.2 前提：要的集合对异或封闭
用基代替原来的数，前提是题目要的就是“任选子集”能异或出的全部值。这个集合对异或封闭：两个子集的异或和再异或，等于两个子集的对称差的异或和，仍是某个子集的异或和。题目一旦限制了能选哪些子集，封闭性就可能没了。
比如 $a = (1, 2, 4)$，规定不能选相邻的两个。合法的选法是不选、只选一个、选第 1 和第 3 个，异或和为 $0, 1, 2, 4, 5$，最大是 5。把这些值插进线性基再求最大，会得到 $1 \oplus 2 \oplus 4 = 7$，可 7 要三个数全选，违反了限制。错在线性基把合法值之间的异或也当成了能取到的值：$1 \oplus 2 = 3$ 对应的选法“第 1 和第 2 个”本身不合法。先确认要的值构成一个对异或封闭的集合（任选子集、一条路径加任意环这类），再用线性基；带选取限制的，先想办法把限制拆掉，拆不掉就换搜索或 DP。
2. 插入：一边插入一边消元
2.1 按最高位存
线性基用一个数组 b[0..59] 存，规定 b[i] 要么是 0，要么是一个最高位恰好是第 $i$ 位的数。插入 $x$ 时从高位往低位看：第 $i$ 位是 1 而 b[i] 空着，就把 $x$ 存进 b[i]；b[i] 已经有数，就令 $x \leftarrow x \oplus b_i$，把第 $i$ 位消成 0，继续看更低的位。
struct XorBasis {
static const int B = 60; // 值都小于 2^60（10^18 < 2^60）
long long b[B] = {}; // b[i]：最高位恰好是 i 的那个数，没有就是 0
int r = 0; // 秩
bool insert(long long x) { // 插入成功（秩加 1）返回 true
for (int i = B - 1; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; r++; return true; }
x ^= b[i];
}
return false; // x 被消成 0：它已经能被异或出来
}
bool contains(long long x) const {
for (int i = B - 1; i >= 0; i--)
if (x >> i & 1) {
if (!b[i]) return false;
x ^= b[i];
}
return true;
}
};
一次插入最多做 60 次异或，$n$ 个数全插完是 $O(60 n)$。
2.2 插入失败，说明它能被异或出来
插入过程中 $x$ 每次异或上的都是基里的数，所以任何时刻都有 $x_{\text{原}} = x_{\text{当前}} \oplus (\text{若干个 } b_i)$。插入有两种结局：
- $x$ 被消成 0：$x_{\text{原}}$ 等于若干个 $b_i$ 的异或，它已经在张成的空间里，
insert返回false，基不变。 - $x$ 停在某个空位
b[i]：存进去的是 $x_{\text{原}}$ 异或上若干个已有的基，张成的空间和直接把 $x_{\text{原}}$ 放进去一样，秩加 1。
存下的数为什么线性无关：它们的最高位两两不同。任取其中一个非空子集异或，最高位最高的那个数在它的最高位上是 1，子集里别的数在这一位都是 0（它们的最高位更低），异或结果在这一位是 1，不可能是 0。
所以插完 $n$ 个数后，b 里的非零数是 $\operatorname{span}(a_1, \dots, a_n)$ 的一组基，个数就是秩 $r$。一个数能不能被异或出来，就是对它走一遍插入的消元，看最后剩不剩 0，这就是 contains。
2.3 和高斯消元的关系
把 $n$ 个数排成一个 $n$ 行 60 列的 0/1 矩阵，插入做的就是模 2 的高斯消元：每个 b[i] 是一行主元在第 $i$ 列的行，“用 b[i] 消掉 $x$ 的第 $i$ 位”是一次行变换。区别在顺序。高斯消元拿到整个矩阵再逐列消；线性基来一行消一行，所以能在线插入。b 按 $i$ 从大到小排是行阶梯形，第 4.2 节的规范化再把它整理成简化行阶梯形。
3. 计数：$2^r$ 种值，每种 $2^{n-r}$ 个子集
3.1 不同的异或值有 $2^r$ 个
基里 $r$ 个数各选或不选，得到 $2^r$ 个异或值，它们两两不同。假如两种不同的选法异或出同一个值，把两个结果再异或一次得到 0，这正好是“两种选法的对称差”的异或和；对称差非空，和线性无关矛盾。基又能异或出空间里的每个值，所以任选子集能异或出的不同值正好 $2^r$ 个，包括空集给的 0。
3.2 每个值都被 $2^{n-r}$ 个子集异或出来
$n$ 个数的子集有 $2^n$ 个，分到 $2^r$ 个不同值上，平均每个值 $2^{n-r}$ 个。实际上每个值都恰好是这么多。
插入时成功的 $r$ 个原数组成一组基（每个都不能被它之前成功的数表示，所以线性无关；失败的数都能被它们表示）。要异或出某个值 $v$：失败的 $n - r$ 个数任选一个子集，异或和记为 $u$，成功的那组基里恰好有一种选法异或出 $v \oplus u$（基的表示唯一，见 3.1），两部分合起来就是 $v$。失败的数怎么选都行，每种选法对应唯一一种补法，一共 $2^{n-r}$ 种。
线性代数的说法：把选法写成 $x \in \{0, 1\}^n$，异或和 $f(x) = x_1 a_1 \oplus \cdots \oplus x_n a_n$ 是线性映射，像的维数是 $r$，由秩-零化度定理，核（异或出 0 的选法）的维数是 $n - r$；异或出 $v$ 的选法是核平移一下，和核一样大。
每个能异或出的值都恰好由 $2^{n-r}$ 个子集得到；异或和为 0 的非空子集有 $2^{n-r} - 1$ 个。 题目问的东西如果是“把全部 $2^n$ 个子集的异或和排起来”，就先把它看成 $2^r$ 个不同的值，每个重复 $2^{n-r}$ 次。
4. 最大值与第 $k$ 小
4.1 最大异或：从高位往低位贪心
比较两个数先比最高位，所以要让结果最大，先让最高位尽量是 1。设当前结果为 $v$，从 $i = 59$ 往下：$v$ 的第 $i$ 位是 0 而 b[i] 非零，就异或上 b[i]。这一步不碰更高的位，因为 b[i] 的最高位就是 $i$；之后也不会把第 $i$ 位改回去，因为后面用到的 b[j]（$j < i$）在第 $i$ 位都是 0。高位优先、每一位能变成 1 就变成 1，最后得到的就是最大值。 写成代码是 v = max(v, v ^ b[i])：第 $i$ 位是 0 时异或后变大，是 1 时变小。
起点不一定是 0。“$s$ 异或上任意子集的最大值”，从 $v = s$ 开始贪心即可，第 6 节图上的路径就要用到。最小值反过来，异或后变小就异或，得到 $s$ 异或上任意子集的最小值。
long long max_xor(long long v = 0) const { // v 异或上任意子集的最大值
for (int i = B - 1; i >= 0; i--) v = max(v, v ^ b[i]);
return v;
}
long long min_xor(long long v) const { // v 异或上任意子集的最小值
for (int i = B - 1; i >= 0; i--) v = min(v, v ^ b[i]);
return v;
}
这两个是 XorBasis 的成员函数，b[i] 为 0 时异或不改变 $v$，不用特判。$s = 0$ 时最小值总是 0（空集），题目要“非空子集的最小值”，见 4.3 末尾。
4.2 规范化：每个主元位只留在一个数里
最大值只关心每一位尽量是 1。第 $k$ 小要的是全部 $2^r$ 个值的排序，b 现在的样子还看不出顺序：高位的基在低位上的 1 会干扰低位的比较。所以先整理一下。把每个非零 b[i] 的最高位 $i$ 叫主元位，规范化就是让每个主元位只出现在自己那个数里：b[i] 在某个更低的主元位 $j$ 上是 1，就异或上 b[j] 把它消掉。
void reduce() { // 规范化：主元位只留在自己那个数里
for (int i = 0; i < B; i++)
for (int j = i - 1; j >= 0; j--)
if (b[j] && (b[i] >> j & 1)) b[i] ^= b[j];
}
i 从小到大处理，轮到 b[i] 时更低的 b[j] 都已经规范好，除了第 $j$ 位不含别的主元位，异或它只会清掉 b[i] 的第 $j$ 位，不会把别的主元位翻回 1。异或上基里的数不改变张成的空间，也不改变 b[i] 的最高位，所以规范化后仍是同一个空间的一组基，仍满足 2.1 的规定。复杂度 $O(60^2)$。
4.3 第 $k$ 小：$k$ 的二进制就是选法
规范化之后，把 $r$ 个基按主元位从低到高编号为 $c_0, c_1, \dots, c_{r-1}$，$c_t$ 的主元位记作 $p_t$。任取一种选法，结果在第 $p_t$ 位上就是“$c_t$ 选了没有”，因为别的基在这一位都是 0。
比较两种不同选法的结果。设 $t$ 是两者选得不一样的编号里最大的那个。高于 $p_t$ 的位只受编号大于 $t$ 的基影响（编号不超过 $t$ 的基，最高位不超过 $p_t$），这些基两边选得一样，所以高于 $p_t$ 的位全相同；第 $p_t$ 位上，选了 $c_t$ 的那边是 1，另一边是 0。所以把选法写成二进制数 $\sum_{t \text{ 被选}} 2^t$，结果的大小顺序和这个二进制数的大小顺序一致：从小到大第 $k$ 个值（$k$ 从 0 数，第 0 个是 0），就是按 $k$ 的二进制位去选基。
long long kth(unsigned long long k) const { // 先 reduce()；k 从 0 数，第 0 个是 0
long long v = 0;
for (int i = 0; i < B; i++)
if (b[i]) { if (k & 1) v ^= b[i]; k >>= 1; }
return k ? -1 : v; // k ≥ 2^r：不存在
}
题面里的“第 $k$ 小”（$k$ 从 1 数）常有两种算法，差别都在 0 和重复值上：
- 只算非空子集、去重：0 能不能由非空子集得到，看有没有插入失败的数。$r < n$ 时能（失败的数和表示它的那些基一起选），这时非空子集的不同值和含空集时一样，答案是
kth(k - 1)；$r = n$ 时不能，要跳过 0，答案是kth(k)。$r$ 是否等于 $n$ 决定 0 算不算，这是这类题最常错的地方。 - 按全部 $2^n$ 个子集算、不去重：每个值重复 $2^{n-r}$ 次（3.2），第 $k$ 个就是不同值里从 0 数的第 $\lfloor (k - 1) / 2^{n-r} \rfloor$ 个。
非空子集的最小值也由此得到：$r < n$ 时是 0，否则是 kth(1)，也就是规范化后主元位最低的那个基。
5. 题目里常见的变形
前四节回答的都是“给一堆数，任选子集”。比赛题很少直接这样问，常见的是把别的结构翻译成这个问题，或者在它上面加一层要求。
5.1 区间的异或：先换成前缀异或
例（CF 1101G）：把数组切成尽量多段，要求任选若干段（至少一段），它们的异或和都不为 0。
设前缀异或 $S_i = a_1 \oplus \cdots \oplus a_i$，$S_0 = 0$。切点 $0 = c_0 < c_1 < \cdots < c_k = n$ 时，第 $j$ 段的异或是 $S_{c_j} \oplus S_{c_{j-1}}$，条件是这 $k$ 个段值线性无关。段值和前缀值可以互相表示：$S_{c_j}$ 等于前 $j$ 段的异或。两组各 $k$ 个数互相能表示，就张成同一个空间；$k$ 个数线性无关，等价于它们张成 $k$ 维，所以
$$ \text{段值线性无关} \iff S_{c_1}, S_{c_2}, \dots, S_{c_k} \text{ 线性无关}. $$问题变成从 $S_1, \dots, S_n$ 里选尽量多的线性无关的数，而且必须选上 $S_n$。$S_n = 0$ 时无解；否则 $\{S_n\}$ 本身线性无关，能扩充成 $S_1, \dots, S_n$ 的一组基，答案就是这 $n$ 个前缀异或的秩。段和区间的异或先写成两个前缀异或的异或，再看前缀异或这组数的线性关系。
5.2 带权选数：按权从大到小插
每个数带一个非负权值，要选出一组线性无关的数使权值和最大。做法是按权值从大到小排序，依次插入，插入成功的就选上。
为什么贪心对。设贪心选出的数按权值排成 $g_1, \dots, g_r$，权值不增；任取一组线性无关的数，也按权值排成 $o_1, \dots, o_m$。先有 $m \le r$：贪心选出的数是全部数的一组基，任何线性无关组都不超过秩。再证每个 $t$ 都有 $w(g_t) \ge w(o_t)$，加起来就得到贪心最优。假设某个 $t$ 上 $w(o_t) > w(g_t)$。$o_1, \dots, o_t$ 是 $t$ 个线性无关的数，$g_1, \dots, g_{t-1}$ 只张成 $t - 1$ 维，所以其中某个 $o_j$（$j \le t$）不能被 $g_1, \dots, g_{t-1}$ 表示。它的权值 $w(o_j) \ge w(o_t) > w(g_t)$，贪心在 $g_t$ 之前就处理过它；当时已选的数都在 $g_1, \dots, g_{t-1}$ 里，表示不出 $o_j$，那 $o_j$ 应该插入成功、成为某个 $g_s$（$s < t$），和“不能被 $g_1, \dots, g_{t-1}$ 表示”矛盾。
// items：(数, 权值)，权值非负。返回线性无关组的最大权值和
long long max_weight(vector<pair<long long, long long>> items) {
sort(items.begin(), items.end(),
[](const auto& p, const auto& q) { return p.second > q.second; });
XorBasis lb;
long long sum = 0;
for (auto [x, w] : items)
if (lb.insert(x)) sum += w;
return sum;
}
线性无关组有交换性质（小的一组总能从大的一组里借一个数扩充），所以按权从大到小贪心插入就是最优。 这个结论下一节还会用到，权值换成位置。
5.3 区间询问：每个主元位留最靠右的
例（CF 1100F）：一个数组，多次询问区间 $[l, r]$ 里任选子集的最大异或。每次询问重建一遍基要 $O(60 \cdot \text{区间长})$，太慢。
做法是从左往右插入，b[i] 旁边多记一个位置 pos[i]。插入第 $p$ 个数时，碰到的 b[i] 位置比 $p$ 小，就把两者交换：新来的留在 b[i]，旧的带着它的位置继续往低位消。插完第 $r$ 个数时的这份基，回答所有右端点为 $r$ 的询问：只用 pos[i] $\ge l$ 的那些 b[i] 贪心。
struct PrefixBasis {
static const int B = 60;
long long b[B] = {};
int pos[B] = {}; // b[i] 记着的位置（从 1 数），越靠右越好
void insert(long long x, int p) {
for (int i = B - 1; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; pos[i] = p; return; }
if (pos[i] < p) { swap(b[i], x); swap(pos[i], p); }
x ^= b[i];
}
}
long long max_xor(int l) const { // 只用位置 >= l 的基：区间 [l, 当前右端点]
long long v = 0;
for (int i = B - 1; i >= 0; i--)
if (pos[i] >= l) v = max(v, v ^ b[i]);
return v;
}
};
为什么只留 pos[i] $\ge l$ 的就对：这是 5.2 的贪心，权值取位置。按位置从大到小插 $a_r, a_{r-1}, \dots$，插完 $a_l$ 时，基已经能表示 $a_l, \dots, a_r$ 里的每个数；再往左插的数，只会填还空着的维度，不会挤掉已有的。所以“按位置从右往左贪心”得到的基里，位置 $\ge l$ 的那部分正好张成 $a_l, \dots, a_r$。交换插入是在线维护这个贪心的结果：新来的数位置最大，应该最先被选，碰到位置更小的就把它往下挤，被挤到消成 0 的是一组线性相关的数里最靠左的那个。每个主元位留最靠右的数，询问 $[l, r]$ 只用位置 $\ge l$ 的部分。 询问按 $r$ 离线排序，只维护一份基，每次询问 $O(60)$。
5.4 合并两组基
两组基合并，就是把一组的每个非零数插进另一组，$O(60^2)$。“一段里所有数的线性基”可以放在线段树、倍增表的节点上，靠合并拼出任意区间或树上路径的基。线性基不支持删除；要删的题，离线成“每个数在哪段时间里存在”，再做线段树分治。
6. 从 0 写一道题：最大 XOR 和路径
题（洛谷 P4151，WC2011）：无向连通图，$n \le 5 \times 10^4$ 个点，$m \le 10^5$ 条边，边权不超过 $10^{18}$，可能有重边和自环。求一条从 1 到 $n$ 的路径，使经过的边权异或和最大；路径可以重复经过点和边，重复经过的边重复计入异或。
6.1 所有路径的异或值是什么集合
能用线性基之前，先看要的集合是不是“某个值异或上一个空间”。路径可以走回头路，一条边走两次等于没走。设 $P$ 是一条固定的从 1 到 $n$ 的路径，$Q$ 是任意另一条。沿 $P$ 去、沿 $Q$ 原路回，是一条回路 $C$，所以 $Q$ 的异或值等于 $P \oplus C$。反过来，任取一条回路 $C$，从 $P$ 的起点 1 出发走到 $C$ 上、绕一圈、原路回到 1，再走 $P$，来回的那段抵消，得到的路径异或值是 $P \oplus C$。所以
$$ \{\text{所有 1 到 } n \text{ 路径的异或值}\} = \{\, P \oplus C \mid C \text{ 是回路的异或值} \,\}, $$回路的异或值对异或封闭（两条回路接起来还是回路，中间来回的一段抵消），是一个空间。答案就是 max_xor(P)，问题只剩下怎么求出回路空间的一组基。
6.2 回路空间的基：每条边一个环
从 1 出发做一遍 BFS（或 DFS），得到一棵生成树，记 $d_u$ 为从 1 沿树边走到 $u$ 的异或和。对回路上的每一步 $u \to v$（边权 $w$），写成
$$ w = d_u \oplus d_v \oplus \underbrace{(d_u \oplus d_v \oplus w)}_{\text{树边上是 } 0}. $$沿一条回路把每一步都这样写开再全部异或起来，$d$ 的部分首尾相接、两两抵消，只剩括号里那项，而它只在非树边上非零。所以任何回路的异或值都是若干个 $d_u \oplus d_v \oplus w$ 的异或；反过来，每个 $d_u \oplus d_v \oplus w$ 本身就是一个回路（树上从 $u$ 到 $v$，再走这条边回来）。把每条边的 $d_u \oplus d_v \oplus w$ 都插进线性基，就得到回路空间的基：树边插进去是 0，不影响；自环和重边不用特判。
答案是从 $d_n$ 出发的最大异或（$d_n$ 就是树上的那条路径 $P$），复杂度 $O((n + m) \cdot 60)$。
6.3 完整程序
#include <bits/stdc++.h>
using namespace std;
struct XorBasis {
static const int B = 60;
long long b[B] = {};
void insert(long long x) {
for (int i = B - 1; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; return; }
x ^= b[i];
}
}
long long max_xor(long long v) const {
for (int i = B - 1; i >= 0; i--) v = max(v, v ^ b[i]);
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> eu(m), ev(m);
vector<long long> ew(m);
vector<vector<pair<int, long long>>> g(n + 1);
for (int i = 0; i < m; i++) {
cin >> eu[i] >> ev[i] >> ew[i];
g[eu[i]].push_back({ev[i], ew[i]});
g[ev[i]].push_back({eu[i], ew[i]});
}
vector<long long> d(n + 1, -1); // 从 1 沿生成树到 u 的异或和，-1 表示还没到过
d[1] = 0;
queue<int> q;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, w] : g[u])
if (d[v] < 0) { d[v] = d[u] ^ w; q.push(v); }
}
XorBasis lb;
for (int i = 0; i < m; i++) lb.insert(d[eu[i]] ^ d[ev[i]] ^ ew[i]); // 树边插进去是 0
cout << lb.max_xor(d[n]) << '\n';
}
写完先和暴力对拍。边权取小于 16 的值时，“当前在哪个点、当前异或值是多少”这个状态只有 $16 n$ 种，从 $(1, 0)$ 出发 BFS 出所有能到的状态，落在点 $n$ 上的那些异或值就是全部路径的异或值，取最大和程序比。能重复走的路径题，状态（点，异或值）在小边权下是有限的，这是现成的暴力。
7. 两道近年的赛题
7.1 CCPC Final 2025 L（Spirited Away）：数不同的区间张成空间
题（QOJ / Universal Cup 3727 L）：多组数据，每组给 $n$ 个小于 $2^{32}$ 的数，$\sum n \le 10^5$。对所有 $1 \le l \le r \le n$ 求 $B(l, r) = \operatorname{span}(a_l, \dots, a_r)$，问一共有多少个不同的集合。
7.1.1 不同的区间只有 $O(32 n)$ 种
区间有 $O(n^2)$ 个，先要缩到能枚举的量。固定右端点 $r$，左端点 $l$ 往左走时空间只会变大，每变一次维数加 1，所以最多变 32 次。变化点就是 5.3 前缀线性基里的那些位置：把插完 $a_r$ 后的基按 pos 从大到小排成 $v_1, \dots, v_k$，位置为 $p_1 > p_2 > \cdots > p_k$，记 $p_{k+1} = 0$，那么
这是 5.3 那句“位置 $\ge l$ 的部分正好张成 $a_l, \dots, a_r$”换了个说法。另外 $a_r = 0$ 时 $l = r$ 给出 $\{0\}$（这时 $p_1 < r$）。固定右端点，左端点往左只经过至多 32 个跳变点，所有区间的空间加起来只有 $O(32 n)$ 个。
7.1.2 两个空间相同，当且仅当规范化后的基相同
同一个空间有很多组基，直接比基不行，得找一个只由空间决定的写法。规范化后的基就是。空间里每个非零数的最高位都是主元位（理由和 2.2 的线性无关证明一样：任何组合的最高位，就是参与组合的基里最高的那个主元位），所以主元位的集合由空间决定。再看主元位 $p$ 上的那个基 $c_p$：规范化之后，它是空间里“主元位中只有第 $p$ 位是 1”的数，而 4.3 说空间里的数由它在主元位上的取值唯一决定，这样的数只有一个。所以 规范化后的基由空间唯一决定，两个空间相同当且仅当规范化后的基相同。把规范化的基哈希成一个 64 位数，最后数有多少种不同的哈希值。
7.1.3 一边插入一边保持规范化
对每个 $r$，按 $v_1, v_2, \dots$ 的顺序往一个空的基里插，每插一个记下当前空间的哈希。如果每次插完都调用 4.2 的 reduce() 再整体哈希，一次是 $O(32^2)$，每个 $r$ 要 $O(32^3)$，太慢。改成插入时就保持规范化：先用已有的基把新数 $y$ 的主元位全部消掉，$y$ 剩下的最高位 $t$ 是一个新主元位；再把已有的基里第 $t$ 位是 1 的都异或上 $y$。这样每插一个是 $O(32)$。哈希取各个基打散之后的和，改动一个基就减去旧的、加上新的。总复杂度 $O(32^2 n)$，$n = 10^5$ 时约 $10^8$ 次简单操作。
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
u64 mix(u64 x) { // splitmix64：把一个数打散成随机的 64 位
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
u32 b[32] = {}; // 5.3 的前缀线性基
int pos[32] = {};
vector<u64> hs; // 每个 (r, j) 对应空间的哈希
for (int r = 1; r <= n; r++) {
u32 x;
scanf("%u", &x);
int p = r;
for (int i = 31; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; pos[i] = p; break; }
if (pos[i] < p) { swap(b[i], x); swap(pos[i], p); }
x ^= b[i];
}
vector<pair<int, u32>> v; // (位置, 基)，按位置从大到小
for (int i = 0; i < 32; i++)
if (b[i]) v.push_back({pos[i], b[i]});
sort(v.rbegin(), v.rend());
if (v.empty() || v[0].first < r) hs.push_back(0); // a_r = 0：B(r, r) = {0}
u32 c[32] = {}; // 规范化的基，一个一个往里插
u64 h = 0;
for (auto [q, y] : v) {
for (int i = 31; i >= 0; i--)
if ((y >> i & 1) && c[i]) y ^= c[i]; // 消掉 y 上已有的主元位
int t = 31 - __builtin_clz(y); // 新的主元位
for (int i = t + 1; i < 32; i++)
if (c[i] >> t & 1) { h -= mix(c[i]); c[i] ^= y; h += mix(c[i]); }
c[t] = y;
h += mix(y);
hs.push_back(h); // l 落在 (下一个位置, q] 时的 B(l, r)
}
}
sort(hs.begin(), hs.end());
printf("%d\n", (int)(unique(hs.begin(), hs.end()) - hs.begin()));
}
}
$O(32 n)$ 个 64 位哈希值里出现碰撞的概率约是 $(3 \times 10^6)^2 / 2^{65}$，可以忽略。
7.2 2026 ICPC 网络赛第二场 A（All Closed）：所有解都必须包含的数
题（QOJ 4113）：有 $n$ 个非空集合 $S_1, \dots, S_n$，元素都在 $[0, 2^m)$ 里，$m \le 20$。一次操作选一个数 $x$，把它同时加进所有集合。用最少的操作让每个集合都对异或封闭，输出要加的那些数。
7.2.1 把“最少操作”换成“最小的空间”
设加进去的数组成集合 $T$，最后第 $i$ 个集合是 $S_i \cup T$。一个非空集合对异或封闭，就包含 $a \oplus a = 0$，又对加法封闭，所以它就是一个空间。看所有最终集合的公共部分：
$$ K = \bigcap_{i} (S_i \cup T) = I \cup T, \qquad I = \bigcap_i S_i . $$若干个空间的交还是空间，所以 $K$ 是一个包含 $I$ 的空间，并且最终集合可以写成 $S_i \cup K$。$T$ 里不必放 $I$ 中的数（它们本来就在每个集合里），所以 $|T| = |K| - |I|$，操作最少等价于 $K$ 最小：求最小的空间 $K \supseteq I$，使每个 $S_i \cup K$ 都是空间，答案是 $K \setminus I$。
7.2.2 每一步加的数都是逼出来的
从 $K = \operatorname{span}(I)$ 开始，任何合法的 $K$ 都包含 $I$、又是空间，所以都包含 $\operatorname{span}(I)$。如果某个 $S_i \cup K$ 不封闭，就有一个数 $x$ 落在 $\operatorname{span}(S_i \cup K)$ 里，却既不在 $S_i$ 也不在 $K$ 里。任取一个包含当前 $K$ 的合法解 $K^*$：$S_i \cup K^*$ 是空间，又包含 $S_i \cup K$，所以包含 $x$；$x$ 不在 $S_i$ 里，只能在 $K^*$ 里。于是每个合法解都包含 $x$，令 $K \leftarrow \operatorname{span}(K \cup \{x\})$，它仍然被每个合法解包含。
每加一个 $x$，$K$ 的秩加 1，至多 $m$ 次后所有 $S_i \cup K$ 都封闭。这时 $K$ 本身合法，又包含于每个合法解，所以它就是最小的那个，答案也因此唯一。求最小的合法解，可以从“每个合法解都必须包含什么”出发，一直加到合法为止，停下时得到的就是最小解。
7.2.3 判断封闭：数元素个数
$S_i \cup K \subseteq \operatorname{span}(S_i \cup K)$，而后者正好有 $2^r$ 个元素（3.1），$r$ 是 $S_i \cup K$ 的秩。所以
$$ S_i \cup K \text{ 封闭} \iff \lvert S_i \rvert + \lvert K \rvert - \lvert S_i \cap K \rvert = 2^r . $$不封闭时，把 $\operatorname{span}(S_i \cup K)$ 列出来（至多 $2^m$ 个），找一个既不在 $S_i$ 也不在 $K$ 里的数，就是要加的 $x$。每轮检查所有集合是 $O(m \sum \lvert S_i \rvert)$，至多 $m$ 轮，再加上每轮 $O(2^m)$ 的列举。
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool insert(vector<int>& b, int x) { // 2.1 的插入，b 有 m 个位置
for (int i = m - 1; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; return true; }
x ^= b[i];
}
return false;
}
vector<int> expand(const vector<int>& b) { // 列出 span(b) 的全部元素
vector<int> all = {0};
for (int i = 0; i < m; i++)
if (b[i]) {
int sz = all.size();
for (int j = 0; j < sz; j++) all.push_back(all[j] ^ b[i]);
}
return all;
}
int main() {
scanf("%d %d", &n, &m);
vector<vector<int>> s(n);
vector<int> cnt(1 << m, 0); // cnt[x]：x 在几个集合里
for (auto& si : s) {
int k;
scanf("%d", &k);
si.resize(k);
for (int& x : si) { scanf("%d", &x); cnt[x]++; }
}
vector<int> kb(m, 0); // K 的基，从 span(I) 开始
for (int x = 0; x < (1 << m); x++)
if (cnt[x] == n) insert(kb, x);
vector<char> inK(1 << m), inS(1 << m);
while (true) {
vector<int> K = expand(kb);
fill(inK.begin(), inK.end(), 0);
for (int x : K) inK[x] = 1;
int forced = -1; // 每个合法解都必须包含的新数
for (int i = 0; i < n && forced < 0; i++) {
vector<int> b = kb;
int common = 0; // |S_i ∩ K|
for (int x : s[i]) { insert(b, x); common += inK[x]; }
int r = 0;
for (int i2 = 0; i2 < m; i2++) r += b[i2] != 0;
long long uni = (long long)s[i].size() + K.size() - common; // |S_i ∪ K|
if (uni == (1LL << r)) continue; // 已经封闭
for (int x : s[i]) inS[x] = 1;
for (int x : expand(b))
if (!inK[x] && !inS[x]) { forced = x; break; }
for (int x : s[i]) inS[x] = 0;
}
if (forced < 0) break;
insert(kb, forced);
}
vector<int> ans; // K \ I
for (int x : expand(kb))
if (cnt[x] < n) ans.push_back(x);
sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int x : ans) printf("%d ", x);
printf("\n");
}
练习
每题后面写的是用到哪一节。
必做
- 洛谷 P3857 彩灯：3.1。
- 洛谷 P4570 元素：5.2。
- LOJ 114 k 大异或和：4.3，注意 0 算不算。
- 洛谷 P4869 albus就是要第一个出场：给值求排名，是 4.3 反过来，再乘上 3.2 的重复次数。
- CF 845G Shortest Path Problem?：第 6 节，求最小值。
- CF 1100F Ivan and Burgers：5.3。
选做
- CF 959F Mahmoud and Ehab and yet another xor task：前 $l$ 个数里异或和为 $x$ 的子集个数，3.2 加离线。
- 洛谷 P3292 幸运数字：树上路径的最大异或，5.4 加树上倍增。
和地图上其他格子的连接
- 2.3 的消元就是模 2 的高斯消元，之后讲高斯消元时，异或方程组的解数（$2^{\text{自由元数}}$）和 3.2 的 $2^{n-r}$ 是同一个数：自由元就是插入失败的那些数。
- A6 的 01-Trie 也求最大异或，它求的是“$x$ 和集合里某一个数异或的最大值”，集合里的数只能选一个；线性基求的是任选子集。题面说“选两个数”用 Trie，说“选若干个数”用线性基。
- 5.2 的贪心是拟阵上的贪心，最小生成树的 Kruskal 是同一个结构（图的无环边集代替线性无关组）。