[hdu3949]XOR(线性基求xor第k小)

题目大意：求xor所有值的第k小，线性基模板题。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long ll;

const int MAX_BASE=;

ll base[],a[],n,m;

//构造线性基，也可用来判断x是否存在，最后返回是否等于0即可。

void getbase(){

  memset(base,,sizeof base);

  for(int i=;i<=n;i++){

      for(int j=MAX_BASE;j>=;j--){

          if(a[i]>>j){

              if(!base[j]){

                base[j]=a[i];

                break;

              }

              a[i]^=base[j];

          }

      }

  }

}

//从高位到低位扫描线性基。如果异或之后答案变大，就把这一位异或到答案。

ll query_max(){

  ll ans=;

  for(int i=MAX_BASE;i>=;i--){

      if((base[i]^ans)>ans){

          ans=base[i]^ans;

      }

  }

  return ans;

}

//从低位到高位扫描线性基。最低位上的线性基即为答案。

ll query_min(){

  for(int i=;i<=MAX_BASE;i++)

      if(base[i]>) return a[i];

}

ll cnt,p[];

//注意0的特殊情况，判断if(n!=cnt)k--;

void rebuild(){

  cnt=;

  for(int i=MAX_BASE;i>=;i--){

    if(!base[i]) continue;

    for(int j=i-;j>=;j--)//还是倒序,一定

      if((base[i]>>j)&)

        base[i]^=base[j];

  }

  for(int i=;i<=MAX_BASE;i++)

    if(base[i])

      p[cnt++]=base[i];

}

ll query_k_max(ll k){

  ll ans=;

  if(k>=(1ll<<cnt)) return -;

  for(int i=MAX_BASE;i>=;i--){

    if((k>>i)&)

      ans^=p[i];

  }

  return ans;

}

int main(){

  int t,tmp;

  scanf("%d",&t);

  for(int _=;_<=t;_++){

    printf("Case #%d:\n",_);

    scanf("%lld",&n);

    for(int i=;i<=n;i++)scanf("%lld",&a[i]);

    getbase();

    rebuild();

    scanf("%d",&m);

    for(int i=;i<=m;i++){

      scanf("%d",&tmp);

      if(n!=cnt) tmp--;

      ll ans=query_k_max(tmp);

      printf("%lld\n",ans);

    }

  }

  return ;

}