线性基模板+例题

一、基础线性基整数异或最常用模板代码#includebits/stdc.husingnamespacestd;在这里插入代码片typedeflonglongll;constintMAX_BIT60;// long long开60int开30ll p[MAX_BIT5];// 插入数字x到线性基voidinsert(ll x){for(intiMAX_BIT;i0;i--){if((xi)1){if(!p[i]){p[i]x;break;}x^p[i];}}// x最后变为0说明x可由现有基异或表示}// 查询集合能异或出的最大值llget_max(){ll res0;for(intiMAX_BIT;i0;i--)if((res^p[i])res)res^p[i];returnres;}// 查询集合能异或出的最小值llget_min(){for(inti0;iMAX_BIT;i)if(p[i])returnp[i];return0;}// 判断x能否由线性基中的数异或得到boolcheck(ll x){for(intiMAX_BIT;i0;i--)if((xi)1){if(!p[i])returnfalse;x^p[i];}returntrue;}// 清空线性基voidclear(){memset(p,0,sizeof(p));}二、带合并操作多组合并线性基// 将b线性基合并进avoidmerge(ll a[],ll b[]){for(intiMAX_BIT;i0;i--)if(b[i])insert(b[i]);}三、求第 k 小异或值进阶模板ll p[MAX_BIT5],d[MAX_BIT5];intcnt;// 线性基有效基底数量voidinsert(ll x){for(intiMAX_BIT;i0;i--){if((xi)1){if(!p[i]){p[i]x;break;}x^p[i];}}}// 重构基底用于求第k小voidrebuild(){cnt0;memset(d,0,sizeof(d));for(inti0;iMAX_BIT;i){for(intj0;ji;j)if((p[i]j)1)p[i]^p[j];if(p[i])d[cnt]p[i];}}// 查询第k小异或值llkth(ll k){ll res0;if(k(1LLcnt))return-1;// 不存在for(inti0;icnt;i)if((ki)1)res^d[i];returnres;}四、使用说明1. 数据范围区分数字范围是int(2^{31})MAX_BIT 30数字范围是long long(2^{63})MAX_BIT 60竞赛绝大多数情况2. 基础操作示例intmain(){clear();ll n,x;cinn;for(inti1;in;i){cinx;insert(x);}coutget_max()endl;// 最大异或return0;}五、线性基核心性质做题必背原数组任意数字异或结果都能等价用线性基异或表示线性基内部任意子集异或结果互不相同线性基不支持删除只能重建删除场景用线段树 / 分块套线性基数组存在 0 的条件插入时数字被消为 0说明该数能被其他数异或凑出。六、经典适用题型给定数组选若干数异或求最大值判断某个数能否由数组子集异或得到求所有子集异或结果中第 k 小区间异或、树上路径异或线段树 / 倍增 线性基。例题牛客多校第二场 BB-Bitwise Maximization_2026牛客暑期多校训练营2中文题面题意给定一个非负整数列表要把每一个数必须分到两个多重集合 A、B 中的其中一个不能不选。定义一个集合的按位异或值集合内所有数做异或运算的结果空集异或值为 0。最终得分 A的异或值 B的异或值你需要求这个得分的最大可能值。做题思路题目要求最大化 X(S⊕X)其中 S 是所有元素的总异或和观察二进制的某一位如果 S 在这一位是1那么不管 X 在这一位是0还是1这一位对总和的贡献始终是一个1因为 X 和 S⊕X必然一个是0一个是1。如果 S 在这一位是0那么 X 和 S⊕XS⊕X 在这一位是相同的。为了让总和最大我们希望 X 在这一位是1这样总和的这一位上就会贡献两个1即 112。原代码直接对 ai建立线性基并最大化 ans这会导致线性基可能为了让 S 为1的某些位变成1而牺牲了让 S 为0的位变成1的机会。这是因为线性基在求max时不区分这些位的重要性但对我们的答案来说SS 为0的位对答案的增加有决定性作用而 SS 为1的位对答案根本没有影响。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintM5e510;inta[M];//列表signedmain(){ios::sync_with_stdio(0);cin.tie(0);intT;cinT;while(T--){intv[65];//线性基memset(v,0,sizeof(v));intn;cinn;intm0,sum0;for(inti0;in;i){cina[i];mmax(m,a[i]);sum^a[i];}intw0;//最大位数while(m){w;m/2;}for(inti0;in;i){a[i]a[i]~sum;for(intjw-1;j0;j--){if(a[i]j1){if(v[j]!0){a[i]a[i]^v[j];}else{v[j]a[i];break;}}}}intans0;for(intiw-1;i0;i--){//coutv[i]:v[i] ;ansmax(ans,ans^v[i]);//coutans:ansendl;}coutans(sum^ans)endl;}}