推荐Menci博客的前半部分:https://oi.men.ci/linear-basis-notes/
非常学术的讲解了线性基。
然后对于如何构造线性基,我一般使用以下方法:
对于每一个加进来的数,从高位向低位扫,若某一位是1,则看线性基的a[i]是否有值,若有,则这个数^=a[i],否则a[i]=这个数,插入完毕。
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; long long ans,a[55],n; void work(long long x){ for(int i=50;i>=0;i--){ if((1ll<<i)&x){ if(a[i]) x^=a[i]; else{ a[i]=x; return; } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ long long x; cin>>x; work(x); } for(int i=50;i>=0;i--){ if((ans^a[i])>ans) ans=ans^a[i]; } cout<<ans; return 0; }