线性基
柒葉灬
2019-05-19 14:55:59
# 线性基
----------
如果一个序列$A$，可以亦或出来的集合为$S$，
那么存在一个序列$B$，使得能亦或出来的集合为$S$。
$B$序列中的数个数是$log_2Max\{A_i\}$
-----
线性基求第K大。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e4+100;
int n;
long long a[65];
bool insert(long long p){
for(int i=62;i>=0;i--){
if(p>>i&1){
if(a[i])p^=a[i];
else {
for(int j=i-1;j>=0;j--)
if(p>>j&1)p^=a[j];
for(int j=i+1;j<=62;j++)
if(a[j]>>i&1)a[j]^=p;
a[i]=p;
return false;
}
}
}
return true;
}
int id,num[65];
int main(){
for(int cas=1,_=(cin>>_,_);cas<=_;cas++){
scanf("%d",&n);
bool isok=0;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
long long x;
scanf("%lld",&x);
isok|=insert(x);
}
id=0;
for(int i=0;i<=62;i++)
if(a[i])num[id++]=i;
printf("Case #%d:\n",cas);
for(int q=(cin>>q,q);q--;){
long long K;
scanf("%lld",&K);
K-=isok;
if(K==0)puts("0");
else if(K>=(1LL<<id))puts("-1");
else{
long long ans=0;
for(int i=0;i<=62;i++)
if(K>>i&1)ans^=a[num[i]];
printf("%lld\n",ans);
}
}
}
return 0;
}
```