【acwing210 异或运算】

【acwing210 异或运算】

题意：

给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，问所有能得到的不同的结果中第k小的结果是多少。

题解：

把所有数插入线性基，把k二进制分解然后把1对应的位置xor起来；注意这样是从第0小=0开始数，需要特判0是否能够被xor出来（insert失败），可以的话需要--k。

代码：

#include<bits/stdc++.h>
#define reg register
using namespace std;
typedef long long ll;
const int MN=60;
ll a[61],tmp[61];
bool flag;
void ins(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
    flag=true;
}
bool check(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}
ll qmax(ll res=0){
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}
ll qmin(){
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}
ll query(ll k){
    reg ll res=0;
    reg int cnt=0;
    k-=flag;//flag=1说明有0，所以要求第k-1位 

    if(!k)return 0;//a[i]只有最高位为1

    for(reg int i=0;i<=MN;i++){

        for(int j=i-1;~j;j--)
            if(a[i]&(1ll<<j))a[i]^=a[j];

        if(a[i])tmp[cnt++]=a[i]; 
    }
    if(k>=(1ll<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1ll<<i))res^=tmp[i];//把1对应的位置xor起来 
    return res;
}
int main(){
    int t;
    cin>>t;
    for(int k=1;k<=t;k++)
    {
        int n;
        ll x;
        printf("Case #%d:\n",k);
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(tmp,0,sizeof(tmp));
        flag=0;
            for(int i=1;i<=n;i++)scanf("%lld",&x),ins(x);
            int q;
            cin>>q;
        while(q--)
        {
            cin>>x;
            printf("%lld\n",query(x));
        } 

    }

    return 0;
}