洛谷P3812 【模板】线性基

 1 //不用高斯消元求线性基 
 2 #include
 3 using namespace std;
 4 typedef long long ll;
 5 const int M=63;
 6 ll p[M];//线性基
 7 bool zero;
 8 
 9 void Insert(ll x){
10     for(int i=M;i>=0;i--)
11         if(x>>i==1)//x的最高位
12             if(p[i]==0){p[i]=x;return ;}//p[i]还没有，p[i]=x 
13             else x^=p[i];//p[i]已经有了，逐个异或 
14     zero=true; //A有异或和为0的组合 
15 }
16 
17 ll qmax(){
18     ll ans=0;
19     for(int i=M;i>=0;i--) ans=max(ans,ans^p[i]);
20     return ans;
21 } 
22 
23 int main(){
24     ll x;int n;scanf("%d",&n);
25     for(int i=1;i<=n;i++) scanf("%lld",&x),Insert(x);
26     printf("%lld\n",qmax());
27     return 0;
28 } 

p[i]存的是二进制下有i位的数。