HDU3949XOR(在线询问给定集合能组成的异或和第k小的值)

题：http://acm.hdu.edu.cn/showproblem.php?pid=3949

题意：题意要找的是去重后的。

分析：对查询的k进行二进制分解位上线性基的异或和

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int M=60;
const int N=1e5+5;
ll q[N];
struct LB{
    ll a[M+2];
    vector<ll>vec;
    void init(){
        for(int i=0;i<=M;i++) a[i]=0;
        vec.clear();
    }
    void Insert(ll x){
        for(int i=M;i>=0;i--){
            if(!(x&(1ll<<i))) continue;

            if(a[i]) x^=a[i];
            else{
                for(int j=0;j<=i-1;j++) if(x&(1ll<<j)) x^=a[j];

                for(int j=i+1;j<=M;j++) if(a[j]&(1ll<<i)) a[j]^=x;

                a[i]=x;
                return ;
            }
        }
    }
    void getvec(){
        for(int i=0;i<=M;i++) if(a[i]) vec.pb(a[i]);
    }
    ll query(ll k,int n){
        if(n!=(int)vec.size()) k--;///代表原集合中有异或和为0的情况，0为最小，所以排序先减去1
        if(k>(1ll<<((int)vec.size()))-1) return -1;
        ll ans=0;
        for(int i=0;i<vec.size();i++) if(k&(1ll<<i)) ans^=vec[i];
        return ans;
    }
}lb;
int main(){
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        int n;
        scanf("%d",&n);
        lb.init();
        for(int i=1;i<=n;i++){
            ll x;
            scanf("%lld",&x);
            lb.Insert(x);
        }
        lb.getvec();
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++) scanf("%lld",&q[i]);
        printf("Case #%d:
",cas);
        for(int i=1;i<=m;i++) printf("%lld
",lb.query(q[i],n));
    }
    return 0;
}