线性基 线性基
（qaq，最近打多校碰到好多线性基的题。而且npy：线性基裸题啊，贴模板。。我：？？？？
学习博客：
https://blog.csdn.net/u013534123/article/details/79875825
https://blog.csdn.net/a_forever_dream/article/details/83654397
例题：洛谷3812
题意：给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 struct Linear_basis{ 5 ll b[55],tot; 6 bool insert(ll x){ 7 for (int i=50;i>=0;i--){ 8 if (x&(1ll<<i)){ 9 if (!b[i]){ 10 b[i]=x; break; 11 } 12 x^=b[i]; 13 } 14 } 15 return x>0; //是否可插入 16 } 17 ll mx(){ 18 ll res=0,ans=0; 19 for (int i=50;i>=0;i--){ 20 res=max(res,res^b[i]); 21 } 22 return res; 23 } 24 }LB; 25 int main(){ 26 int n;scanf("%d",&n); ll x; 27 for (int i=1;i<=n;i++){ 28 scanf("%lld",&x); 29 LB.insert(x); 30 } 31 ll ans=LB.mx(); 32 printf("%lld ",ans); 33 return 0; 34 }
线性基模板整理：
1 struct Linear_basis{ 2 ll b[55],tot; 3 bool insert(ll x){ 4 for (int i=50;i>=0;i--){ 5 if (x&(1ll<<i)){ 6 if (!b[i]){ 7 b[i]=x; break; 8 } 9 x^=b[i]; 10 } 11 } 12 return x>0; //是否可插入 13 } 14 ll mx(){ 15 ll res=0; 16 for (int i=50;i>=0;i--){ 17 res=max(res,res^b[i]); 18 } 19 return res; 20 } 21 ll mn(){ 22 ll res=INF; 23 for (int i=50;i>=0;i--){ 24 res=min(res,res^b[i]); 25 } 26 return res; 27 } 28 }LB; 29 //线性基求并 30 Linear_basis merge(Linear_basis p,Linear_basis q){ 31 Linear_basis tmp=p; 32 for (int i=32;i>=0;i--){ 33 if (q.b[i]) tmp.insert(q.b[i]); 34 } 35 return tmp; 36 } 37 //线性基求交 38 Linear_basis intersection(Linear_basis p,Linear_basis q){ 39 Linear_basis ans,c=q,d=q; ans.clear(); 40 for (int i=0;i<=32;i++){ 41 ll x=p.b[i]; 42 if(!x) continue; 43 int j=i; 44 ll tmp=0; 45 for(;j>=0;j--){ 46 if((x>>j)&1){ 47 if(c.b[j]) {x^=c.b[j];tmp^=d.b[j];} 48 else break; 49 } 50 } 51 if(!x) ans.b[i]=tmp; 52 else {c.b[j]=x;d.b[j]=tmp;} 53 } 54 return ans; 55 }