一、什么是线性基1. 从向量基底说起在线性代数中三维空间中任意向量都可以用(1,0,0), (0,1,0), (0,0,1)线性组合表示这三个向量线性无关构成了一组基2. 异或世界里的向量在异或运算中每个整数可以看作一个二进制向量例如5 (101)_2是一个 3 维向量异或XOR就是模 2 加法线性基用最少的一些数使得它们的异或组合能表示原数组中所有数的异或结果。二、严格定义定义给定数组a[1...n]其线性基是一个集合B满足可表示性a中任意多个数的异或和都能由B中若干数异或得到极小性B中任意元素都不能被其他元素异或表示线性无关唯一性经过标准化后线性基的形式是唯一的等价表述设原数组所有数构成的集合为S则span(B){x1⊕x2⊕⋯⊕xk∣xi∈B}{ai1⊕ai2⊕⋯∣aij∈S}三、线性基的构造原理核心思想高斯消元线性基本质上是对二进制矩阵做行简化阶梯形Row Echelon Form。插入一个数 x 的过程for i 从最高位 downto 0: if x 的第 i 位是 1: if d[i] 不存在: d[i] x; break; // 成功插入 else: x ^ d[i]; // 消去第 i 位继续尝试为什么这样做是对的操作意义x ^ d[i]利用已有的基向量消除当前位的 1d[i] x新增一个线性无关的向量循环结束x 被完全消为 0说明它可以被现有基表示几何理解原数空间: {x₁, x₂, x₃, ...} ↓ 插入/消元 基空间: {d[k], d[k-1], ..., d[0]} ↑ 维度更低但表达能力相同四、线性基的性质非常重要性质 1维数 ≤ 位数对于 32 位整数线性基最多有32 个元素。这是算法高效的根本原因性质 2零向量的表示线性基本身不含 0但如果插入失败某数被完全消去说明存在子集异或为 0性质 3最大异或和从高位到低位贪心result 0 for i from high downto low: if (result XOR d[i]) result: result ^ d[i]性质 4子集异或的值域大小设线性基中有r个元素则能表示的不同异或值有2ʳ 个包括 0不包括 0 则有2ʳ − 1 个五、标准代码模板带注释struct LinearBasis { static const int MAXL 60; // 支持到 2^61-1 long long d[61]; // d[i]: 最高位为 i 的基 bool zero; // 能否异或出 0 LinearBasis() { memset(d, 0, sizeof(d)); zero false; } // 插入一个数 bool insert(long long x) { for (int i MAXL; i 0; --i) { if (!(x i 1)) continue; if (!d[i]) { d[i] x; return true; } x ^ d[i]; } zero true; // x 被消为 0说明存在异或为 0 的子集 return false; } // 查询最大异或和 long long query_max() { long long res 0; for (int i MAXL; i 0; --i) { if ((res ^ d[i]) res) { res ^ d[i]; } } return res; } // 查询最小非零异或值 long long query_min() { if (zero) return 0; for (int i 0; i MAXL; i) { if (d[i]) return d[i]; } return 0; // 空基 } };例子数组[7, 5, 3]Step 1写出二进制数二进制711151013011Step 2构建线性基插入过程插入 7 (111)i 2: bit1, d[2]0 → d[2]7插入 5 (101)i 2: bit1, d[2]7 → x ^ 7 → 101 ^ 111 010 (2) i 1: bit1, d[1]0 → d[1]2插入 3 (011)i 2: bit0 → skip i 1: bit1, d[1]2 → x ^ 2 → 011 ^ 010 001 (1) i 0: bit1, d[0]0 → d[0]1六、进阶第 k 小异或值为什么需要重构普通线性基中d[i]之间不是完全独立的高位可能依赖低位不能直接按位取。重构过程高斯消元标准化void rebuild() { // 上三角化让每个 d[i] 只控制第 i 位 for (int i MAXL; i 0; --i) { for (int j i - 1; j 0; --j) { if (d[i] j 1) { d[i] ^ d[j]; } } } // 收集非零基 cnt 0; for (int i 0; i MAXL; i) { if (d[i]) p[cnt] d[i]; } }查询第 k 小long long kth(long long k) { if (zero) k--; // 第 1 小是 0 if (k (1LL cnt)) return -1; // 不存在 long long res 0; for (int i 0; i cnt; i) { if (k i 1) { res ^ p[i]; } } return res; }原理图解重构后p[0], p[1], p[2], ... 对应关系 k 1011₂ p[0] ^ p[1] ^ p[3] 每个 bit 独立控制一个基向量 ✓七、线性基的合并方法一暴力插入常用LinearBasis merge(LinearBasis a, LinearBasis b) { LinearBasis res a; for (int i MAXL; i 0; --i) { if (b.d[i]) { res.insert(b.d[i]); } } return res; }方法二启发式合并多线性基适用于线段树、分治等场景。八、经典应用场景1. 最大异或和最基础给 n 个数选若干个数异或求最大值解法建线性基贪心取最大值2. 第 k 小异或值HDU 3949解法重构 二进制拆分3. 查询能否异或得到某值bool can_get(long long x) { for (int i MAXL; i 0; --i) { if (!(x i 1)) continue; if (!d[i]) return false; x ^ d[i]; } return x 0; }4. 区间异或最值给数组多次询问区间 [l, r] 的最大异或和解法线段树 线性基合并或离线 前缀线性基5. 最大化数组和核心技巧x ~total_xor; // 限制搜索空间在约束子空间中求最大值九、常见坑点总结坑点说明忘记处理 0zero标志位很重要位数不够根据题目范围调整 MAXL未重构就查第 k 小必须先 rebuild合并顺序一般从高位到低位插入long long 溢出移位时注意符号十、复杂度分析操作时间复杂度空间复杂度插入O(log C)O(log C)查询最大O(log C)-查询第 k 小O(log C)-合并O((log C)²)O(log C)其中C是数值范围。十一、一句话总结线性基是用 O(log C) 的空间保存了一个数组所有异或子集的信息并能高效回答最大/最小/第 k 小/存在性等问题的数据结构。小羊有一个非负整数列表和两个空的多重集合。他需要将列表中的每个整数放入两个多重集合之一。 注意多重集合可以包含重复的值。 为了给小羊的工作评分他的领导分别计算两个多重集合的按位异或XOR值并将结果相加得 到最终得分。小羊希望最大化得分你能告诉他最高能得多少分吗 一个多重集合的按位异或值为这个集合的异或和。空的多重集合的按位异或值视为0。 输入格式 每个测试包含多组测试用例。第一行包含测试用例数T1⩽T ⩽104。接下来是每组测试用例的描 述。 每组测试用例的第一行包含一个整数n1⩽n⩽5×105——列表的长度。 每组测试用例的第二行包含n个整数a1,a2,...,an0⩽ai 230——列表中的元素。 保证所有测试用例的n之和不超过5×105。 输出格式 对于每组测试用例输出一个整数表示最大得分两个集合的异或和的异或和显然是整个数组的异或和S。 考虑整个数组的异或和结果对于这个结果中那些是 1 的位无论我们 怎么分集合一定都是一个集合是 0 另一个集合是 1 不受影响。 而对于剩下的位我们应该从高到低让每一位尽可能为 1 。推理当S的0位那么一定是0或者22的倍数个本位1得到的根据只剩这些位的处理过的x得到的线性基一定是可以得到的合法最大异或和M但是由于最后这些位变成S后是0所以另一个组合对应这些位一定和M是一样的因为M^M0.对于每个元素进行与S比较去除S已经是1的位置的1把处理过的元素构建线性基寻找最大可以推得答案等于S2*MM为处理过的元素能构成的最大异或和#include bits/stdc.h using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin t; while (t --) { int n; cin n; vectorint nums(n); for (auto v: nums) cin v; int total_xor 0; for (auto v: nums) total_xor ^ v; vectorint xor_base(30, 0); for (auto x: nums) { x ~total_xor; for (int i 29; i 0; i --) { if (x i 1) { if (xor_base[i]) x ^ xor_base[i]; else { xor_base[i] x; break; } } } }//用处理过的x构建线性基 int maximized 0; for (int i 29; i 0; i --) { if ((maximized ^ xor_base[i]) maximized) { maximized ^ xor_base[i]; } }//最大 cout total_xor 2 * maximized \n;//推论 } return 0; }