线性基模板
作者:
清蒸小烧卖
,
2022-07-29 13:41:36
,
所有人可见
,
阅读 212
线性基
集合中取若干数,使得其异或最大,且数的个数最少
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll p[N];
void insert(ll x)//从最高位开始寻找
{
for(int i=62;i>=0;i--)
{
if(x>>i&1)
{
if(!p[i]) {p[i]=x;break;}
else x^=p[i];
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll x;
for(int i=0;i<=62;i++) p[i]=0;
for(int i=1;i<=n;i++) cin>>x,insert(x);
ll ans=0;
for(int i=62;i>=0;i--)
{
if((ans^p[i])>ans) ans^=p[i];
}
cout<<ans<<endl;
}
}