常见算法题型之数论进阶：线性基

常见算法题型之数论进阶线性基线性基是算法竞赛中专门处理子集异或和问题的核心数据结构它通过构造一组线性无关的基底将原集合所有可能的异或组合压缩到与二进制位数同级的空间中能在O(log⁡V)O(\log V)O(logV)的时间内完成各类查询是处理异或问题的必备工具。一、基础概念与性质1. 异或运算核心性质线性基的所有操作都基于异或的基本性质交换律a⊕bb⊕aa \oplus b b \oplus aa⊕bb⊕a结合律(a⊕b)⊕ca⊕(b⊕c)(a \oplus b) \oplus c a \oplus (b \oplus c)(a⊕b)⊕ca⊕(b⊕c)自反性a⊕a0a \oplus a 0a⊕a0a⊕0aa \oplus 0 aa⊕0a关键推论若a⊕bca \oplus b ca⊕bc则等价于ab⊕ca b \oplus cab⊕c、ba⊕cb a \oplus cba⊕c2. 线性基的定义对于一个非负整数集合它的线性基BBB是满足以下条件的特殊数集张成性原集合的任意一个子集的异或和都可以由BBB中若干个数异或得到线性无关性BBB的任意非空子集的异或和都不为 0即没有冗余元素规范性BBB中第jjj个元素若存在的二进制最高位为第jjj位且其他元素的第jjj位均为 0。3. 核心性质线性基的大小不超过数值的二进制位数int范围最多 32 个long long最多 64 个线性基不唯一但基底数量固定能表示的异或和集合完全一致线性基本身无法直接表示 0若原集合存在非空子集异或和为 0插入过程中会出现数值被消为 0 的情况。二、线性基的构造插入操作1. 构造原理逐个将原集合的数插入线性基从最高位向最低位处理若当前位已有基底则用基底消去当前数的这一位直到数变为 0可被已有基底表示或找到空位完成插入。2. 分步插入流程设线性基数组为b[]b[j]表示最高位为第jjj位的基底当前插入数为xxx从最高位如 31 位到 0 位倒序遍历二进制位若xxx的第jjj位为 0直接跳过若b[j]为空值为 0则令b[j] x插入成功结束流程若b[j]已存在则令x ^ b[j]消去xxx的第jjj位继续循环若最终xxx变为 0说明该数可被已有线性基表示插入失败。3. 插入代码片段int 版intb[32];// 存储线性基b[j]对应最高位为j的基底// 向线性基插入一个数xvoidinsert(intx){for(intj31;j0;j--){if((xj)1){// 当前位为1if(!b[j]){// 该位无基底直接插入b[j]x;break;}x^b[j];// 用基底消去当前位}}// 若x最终为0说明原集合可异或出0}三、核心查询操作1. 判定数值能否被表示用途判断一个数valvalval是否等于原集合某个子集的异或和。方法模拟插入过程用valvalval逐位消去基底若最终结果为 0 则可以表示否则不能。boolcheck(intval){for(intj31;j0;j--){if((valj)1){if(!b[j])returnfalse;// 无对应基底无法表示val^b[j];}}returnval0;}2. 求最大异或和用途求原集合所有子集异或和的最大值。方法贪心思想从高位到低位遍历若异或当前基底后结果变大则选择该基底。intquery_max(){intres0;for(intj31;j0;j--){if(b[j](res^b[j])res){res^b[j];}}returnres;}3. 求最小非零异或和用途求原集合所有非空子集异或和的最小值。方法线性基中最低位的非零基底就是答案。intquery_min(){for(intj0;j31;j){if(b[j])returnb[j];}return0;// 空集情况根据题意调整}4. 补充能否异或出 0线性基本身不能表示 0需额外标记若插入过程中任意一个数被消为 0则原集合存在非空子集异或和为 0。四、模板例题精讲题目链接https://ac.nowcoder.com/acm/problem/179681. 题意重述给定nnn个数QQQ次询问每次给出 (x,y)问能否选择若干个数与xxx异或任意多次最终得到yyy。2. 思路转化根据异或自反性题目等价于是否存在子集SSS满足x⊕(S的异或和)yx \oplus (\text{S的异或和}) yx⊕(S的异或和)y两边同时异或xxx得到S的异或和x⊕y\text{S的异或和} x \oplus yS的异或和x⊕y问题直接转化为判断x⊕yx \oplus yx⊕y能否被原集合的子集异或表示这正是线性基的基础查询场景。3. 代码详解对应你提供的标准正解代码核心逻辑拆解如下#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,q;cinn;vectorinta(n);for(inti0;in;i)cina[i];vectorintb(32);// 线性基主体// w、id数组用于记录构造方案本题不需要输出方案可忽略vectorintw(32),id(32);// 构造线性基for(inti0;in;i){intxa[i],tmp0;for(intj31;j0;j--){if((xj)1){if(!b[j]){b[j]x;id[j]i;w[j]tmp^(1j);break;}x^b[j];tmp^w[j];}}}cinq;while(q--){intx,y;cinxy;inttagx^y;// 核心转化判断tag能否被表示if(!tag){// tag为0无需选数直接成立coutYES\n;continue;}boolfailfalse;inttmp0;for(intj31;j0;j--){if((tagj)1){if(!b[j]){// 无对应基底无法表示failtrue;break;}tag^b[j];tmp^w[j];}}if(fail)coutNO\n;elsecoutYES\n;}return0;}4. 复杂度分析构造线性基O(n×log⁡V)O(n \times \log V)O(n×logV)VVV为数值最大值int 下log⁡V32\log V 32logV32单次查询O(log⁡V)O(\log V)O(logV)总复杂度O((nQ)log⁡V)O((nQ)\log V)O((nQ)logV)在n,Q≤105n,Q \le 10^5n,Q≤105的数据下完全满足时限要求。五、完整通用模板long long 版覆盖绝大多数线性基题型可直接复用#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAX_BIT63;// long long 范围 0~62位ll basis[MAX_BIT];boolhas_zero;// 是否能异或出0// 插入数xvoidinsert(ll x){for(intiMAX_BIT-1;i0;i--){if((xi)1){if(!basis[i]){basis[i]x;return;}x^basis[i];}}has_zerotrue;// x被消为0可异或出0}// 判断x能否被表示boolcheck(ll x){for(intiMAX_BIT-1;i0;i--){if((xi)1){if(!basis[i])returnfalse;x^basis[i];}}returntrue;}// 查询最大异或和llquery_max(){ll res0;for(intiMAX_BIT-1;i0;i--){if(basis[i](res^basis[i])res){res^basis[i];}}returnres;}// 查询最小非零异或和llquery_min(){if(has_zero)return0;for(inti0;iMAX_BIT;i){if(basis[i])returnbasis[i];}return0;}六、常见应用场景子集异或和的存在性、最值、第k小问题树上路径异或和结合前缀异或转化为两点异或博弈论中的 Nim 游戏变种、公平组合游戏集合异或合并、带删除的线性基离线处理等进阶问题。