线性基的概念与构造
极难3线性基：异或世界的“骨干”工具
你有没有想过，如果给你一堆数字，只用异或（⊕）运算，你能组合出多少种结果？比如班费买东西，你手里有 5 元、8 元、10 元，但老师只允许你每次选几个数字，把它们异或起来得到最终金额，你能表示出哪些金额？其实，我们不需要记住所有组合，只需要找出几个“骨干”数字，它们就能代表所有可能的结果。这些骨干数字组成的集合就叫做线性基。
线性基专门用来处理异或运算的问题。它就像一个最小工具箱：里面工具不多，但每个工具都是独一无二的，用它们可以拼出所有原来集合能异或出的数。常用于解决“最大异或和”、“能否异或出某个数”、“合并两个集合的异或能力”等问题。
1. 从“猜数游戏”理解线性基
场景： 老师心里想了一个数（比如 7），同学们可以任意报几个数，然后把这些数异或起来，看能不能正好得到 7。但是老师不会告诉你答案，只告诉你“能”或“不能”。
你手里有 10 个数，要逐个尝试所有组合吗？太麻烦了！聪明的方法是：从这 10 个数中挑出几个骨干数，它们能组合出的结果和原来 10 个数能组合出的结果完全一样。这些骨干数就是线性基。
生活中的类比：
- 你有一盒积木（原集合），但有些积木可以用其他积木拼出来。你最后只留下那些不能互相拼出来的积木（基），它们就能拼出所有可能的造型。
- 你的零花钱有 3 元、5 元、6 元。用它们异或（注意不是加法哦）能得到的金额有：0、3、5、6、3⊕5=6、3⊕6=5、5⊕6=3、3⊕5⊕6=0。看，其实只有 4 种不同的结果：0、3、5、6。其中 6 可以等于 3⊕5，所以真正的“骨干”就是 3 和 5。用 3 和 5 就能异或出 0、3、5、6 了。
2. 数学原理：二进制世界里的向量
在计算机里，整数是用二进制表示的。比如 5（二进制 101）可以看作一个三维向量 (1,0,1)（第2位=1，第1位=0，第0位=1）。
异或运算相当于模2加法：0⊕0=0，0⊕1=1，1⊕0=1，1⊕1=0。和向量加法很像，只是没有进位。
一组数的线性组合，就是每个数选或不选（选表示用1次，不选表示0次），然后全部异或起来。因为异或只能选一次或零次（再异或一次就抵消了），所以系数只能是 0 或 1。
线性基就是这组数张成的空间的一组基，它满足三个条件：
- 线性无关：基中任何一个数都不能被其他基向量异或得到。
- 能生成所有结果：原来的所有数能异或出的结果，用基也能完全一样地异或出来。
- 个数最少：基的大小等于原集合的秩（最大线性无关组的大小）。
3. 如何构造线性基？——贪心插入法
我们用一个数组 basis 来存放基向量，其中 basis[i] 表示最高位（最高二进制1）在第 i 位的基向量。比如 basis[3] 里存的数的最高位是第3位（对应 2³=8）。
我们从高位到低位处理每个要插入的数。
插入算法步骤：
- 从最高位（比如第 31 位）向下扫描当前数 x。
- 如果 x 的当前位是 1：
- 检查
basis[该位]是否存在（不为0）。 - 如果不存在，就把 x 放进
basis[该位]，插入结束。 - 如果存在，就让 x 异或上
basis[该位]（消去这一位），继续检查更低位。
- 检查
- 如果最后 x 变成 0，说明 x 能被已有的基表示出来，就不加入新向量。
形象理解：
每个基向量就像一把“高位消除锤子”。遇到新数，如果它最高位的锤子已经有了，就用那个锤子敲掉它的最高位，再看它剩下的部分。如果剩下的部分出现了一个新高位——没有人有这个高位的锤子，那就把它存起来当新锤子。
举例：集合 {3, 5, 6}
用二进制表示：
- 3 = 011（最高位是第1位，2¹=2）
- 5 = 101（最高位是第2位，2²=4）
- 6 = 110（最高位是第2位，2²=4）
插入过程：
- 插入 3 (011)：检查最高位第1位，
basis[1]原来为空，所以存入basis[1] = 3。 - 插入 5 (101)：最高位第2位，
basis[2]为空，存入basis[2] = 5。 - 插入 6 (110)：最高位第2位，
basis[2]已经有5了，所以x = 6 ⊕ 5 = 3（011）。现在 x 最高位变为第1位，basis[1]已经有3了，所以x = 3 ⊕ 3 = 0。x 变成0，说明 6 能被基表示（6 = 5 ⊕ 3），不插入。
最终基：{3, 5}。
用它们能异或出的结果：0（什么都不选）、3、5、3⊕5=6。正好是原集合能得到的所有结果。
4. 新手容易犯的错误
错误1：插入时忘记从高位到低位扫描
如果你从低位向高位处理，可能会把高位的1保留下来，导致基不是最简形式。一定要从最高位向最低位消去。
错误2：认为线性基只能处理正数
其实负数也可以，但通常我们只考虑非负整数，且用 int 或 long long 存储。如果考虑负数，要小心符号位，但主流竞赛中线性基都是在非负整数下使用的。
错误3：误以为线性基元素个数等于原集合个数
不是的！线性基大小最多是二进制位数（比如 32 位整数最多 32 个），原集合可能有 1000 个数，但线性基可能只有几十个。它是精简后的结果。
错误4：插入时用 x ^= basis[i] 后忘记更新当前位
有些同学在循环中直接写 if (x>>i & 1)，然后 x ^= basis[i]，但没注意 x 的最高位已经变了，下次循环应该重新找最高位。所以通常用 for 循环从高到低，每次只检查当前位即可。
5. 完整可运行的代码示例（C++）
下面这段代码实现了线性基的插入，并判断一个数是否能被表示出来。注释已经写得很清楚，适合初学者理解。
#include <bits/stdc++.h>
using namespace std;
const int MAXB = 60; // 假设数值不超过 2^60，60 位足够了
class LinearBasis {
public:
long long basis[MAXB]; // basis[i] 存储最高位为第 i 位的基向量
LinearBasis() {
for (int i = 0; i < MAXB; i++) {
basis[i] = 0;
}
}
// 插入一个数 x，成功返回 true，否则 false（表示 x 能被已有基表示）
bool insert(long long x) {
// 从高位向低位扫描
for (int i = MAXB - 1; i >= 0; i--) {
// 检查 x 的第 i 位是否为 1
if (x & (1LL << i)) {
// 如果这一位还没有基向量
if (basis[i] == 0) {
basis[i] = x; // 存入当前基
return true; // 插入成功
} else {
x ^= basis[i]; // 消去这一位的 1
}
}
}
// x 被完全消为 0，说明能被表示
return false;
}
// 判断一个数 y 能否被当前线性基表示
bool canRepresent(long long y) {
for (int i = MAXB - 1; i >= 0; i--) {
if (y & (1LL << i)) {
if (basis[i] == 0) return false; // 没有对应的高位，无法表示
y ^= basis[i];
}
}
return y == 0;
}
// 查询线性基能异或出的最大值
long long queryMax() {
long long ans = 0;
for (int i = MAXB - 1; i >= 0; i--) {
// 如果 ans 当前这一位是 0，则异或上 basis[i] 能让这一位变成 1
if ((ans ^ basis[i]) > ans) {
ans ^= basis[i];
}
}
return ans;
}
};
int main() {
// 举例：集合 {3, 5, 6}
vector<long long> nums = {3, 5, 6};
LinearBasis lb;
for (long long num : nums) {
if (lb.insert(num)) {
cout << num << " 插入成功（是新基向量）" << endl;
} else {
cout << num << " 能被已有基表示，不插入" << endl;
}
}
// 测试表示能力
cout << "能否表示 4？ " << (lb.canRepresent(4) ? "能" : "不能") << endl; // 不能
cout << "能否表示 6？ " << (lb.canRepresent(6) ? "能" : "不能") << endl; // 能
// 最大异或和
cout << "能异或出的最大值: " << lb.queryMax() << endl; // 5⊕3=6，最大值是 6
return 0;
}
运行结果：
3 插入成功（是新基向量）
5 插入成功（是新基向量）
6 能被已有基表示，不插入
能否表示 4？ 不能
能否表示 6？ 能
能异或出的最大值: 6
6. 相关指引
学完了线性基的构造，下一步可以探索：
- 求第 k 小异或和：把线性基进一步化简（变成“最简阶梯形”），然后用类似二进制枚举的方法得到所有异或值中第 k 小的那个。
- 合并两个线性基：把一个线性基的所有元素插入到另一个线性基中，相当于把两个集合的异或能力合并。
- 线性基与高斯消元：线性基的构造本质上是高斯消元在异或空间中的特例，你可以把每个数写成一个二进制矩阵，然后做行最简形。不过线性基更简单、更常用。
如果你对异或运算还不熟悉，可以先复习一下异或的性质：
- 同一个数异或两次等于 0（a ⊕ a = 0）
- 异或满足交换律和结合律
- a ⊕ b = c 等价于 a = b ⊕ c
线性基是竞赛中处理异或问题的利器，掌握它，很多难题都会迎刃而解。试试自己构造一个 64 位的线性基，再拿两个大数挑战一下！
例题精讲
关于线性基，以下哪个说法是正确的？
给定一组整数，构造出的线性基的大小（基中元素个数）一定等于原集合中所有不同数的个数。
在构造线性基的过程中，当插入一个数x时，如果某一位i（从高到低）上x为1，且该位已有基向量p[i]，则应该执行以下哪个操作？
以下是用线性基求最大异或和的框架，请补全插入函数。假设p[0..MAX_BIT]初始化为0。
void insert(int x) {
for (int i = MAX_BIT; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (___①___) {
p[i] = x;
break;
}
x ^= p[i];
}
}
int query_max() {
int res = 0;
for (int i = MAX_BIT; i >= 0; i--) {
if ((res ^ p[i]) > res) res ^= p[i];
}
return res;
}有两个线性基A和B，分别代表两个整数集合的异或空间。现要将B合并到A中，得到合并后的线性基C。以下关于合并操作的描述，正确的是？