题意:多组数据.每组数据给定n个整数,然后询问m次,每次询问给定一个整数k,求从(a_1,a_2,a_3...a_n)中选出若干个数执行异或运算能够得到的整数集合中(去掉重复的数),第k小的数是多少?((1<=n,m<=10000,1<=a_i,k<=10^{18}))
分析:直接先构建出这n个数的线性基,然后类似于高斯消元构建出简化阶梯型矩阵,保证线性基的每一位,只有一个数的该位是1.最后对k进行二进制拆分,如果这一位是1,就异或线性基中对应的数.
有几个细节就是因为我们的线性基是可以自己异或自己,即可以得出0的,然而本题并不支持自己异或自己的操作,所以如果线性基中有0,则让k--,然后再进行二进制拆分.
然后,若线性基中有cnt个数,则可以异或出(2^{cnt})个不同的数,那么如果(k>=2^{cnt}),则无解.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
LL cnt,a[10005],b[65];
void Guass(int n){
memset(b,0,sizeof(b));cnt=0;//多组数据初始化
//线性基模板
for(int i=1;i<=n;i++)
for(int j=63;j>=0;j--)
if((a[i]>>j)&1){
if(!b[j]){
b[j]=a[i];
break;
}
else a[i]^=b[j];
}
//高斯消元,消去线性基中其它该位上也是1的数
for(int i=63;i>=0;i--){
if(!b[i])continue;
for(int j=i+1;j<=63;j++)
if((b[j]>>i)&1)b[j]^=b[i];
}
for(int i=0;i<=63;i++)
if(b[i])b[cnt++]=b[i];
}
int main(){
int T=read();
for(int Case=1;Case<=T;Case++){
printf("Case #%d:
",Case);
int n=read();for(int i=1;i<=n;i++)a[i]=read();
Guass(n);
int m=read();
while(m--){
LL k=read();if(n>cnt)k--;
//一共有n个数,如果线性基中的数不足n个,则存在自己异或自己得到0
if(k>=(1ll<<cnt))puts("-1");//特判
else{
LL ans=0;
for(int i=0;i<=63;i++)
if((k>>i)&1)ans^=b[i];//二进制拆分k
printf("%lld
",ans);
}
}
}
return 0;
}