如题,排序后用cpy存储原数组复制,对原数组作高斯消元求线性基,对于选中的线性基的和存入xum...但是只对了前三个点
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
/*
高斯消元法求异或空间线性基:
A)从高到低枚举每一列c:
(1)找到一个二进制第c位是1的数
(2)将这个数换到第c个
(3)将所有第c位是1的数与该数异或
复杂度O(n^2),但数字需要在ull范围内
*/
ull deg(ull num, int i){return num & (1ull << i);}
int gauss_xor(vector<ull> &x){
vector<ull>cpy(x);
ull xum = 0;
int n=x.size()-1;
int c,r;
for(c=63,r=1; ~c && r<=n; c--){
//(1)(2)
for(int i=r;i<=n;i++)
if(deg(x[i],c)){
swap(cpy[r],cpy[i]);
swap(x[r],x[i]);
cout<<cpy[r]<<endl;
xum+=cpy[r];
break;
};
if(!deg(x[r],c))continue;
//(3)
for(int i=1;i<=n;i++)
if(i!=r && deg(x[i],c))
x[i]^=x[r];
r++;
}
//x.resize(--r);
return xum;
}
//https://www.luogu.com.cn/problem/P3812
signed main(){
vector<ull> a;
int n;cin>>n;
a.resize(n+1);
ull xum=0,sum =0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
sort(a.begin()+1,a.begin()+n+1,[](int a,int b){
return a>b;
});
xum=gauss_xor(a);
cout<<sum-xum<<endl;
}