LOJ114 k大异或和

传送门

(vjudge和hdu也有但是我觉得LOJ好看！而且限制少！)

不过本题描述有误，应该是k小。

首先我们需要对线性基进行改造。需要把每一位改造成为，包含最高位的能异或出来的最小的数。

为啥呢？因为如果不满足这个条件的话，那么在之后的异或过程中，大的数反而会被小的数异或的更小。

满足了上述性质之后，我们就能知道，首先高位的1一定比低位的1更能使异或和变大，而低位的1一定能使异或和变大。那么我们先把线性基中所有元素压入栈，之后把k二进制拆分，异或上对应的位置的值即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

#define rep(i,a,n) for(register int i = a;i <= n;i++)

#define per(i,n,a) for(register int i = n;i >= a;i--)

#define enter putchar('\n')

#define pr pair<int,int>

#define mp make_pair

#define fi first

#define sc second

#define I inline

using namespace std;

typedef long long ll;

const int M = 20005;

const int N = 10000005;

ll read()

{

   ll ans = 0,op = 1;char ch = getchar();

   while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

   while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();

   return ans * op;

}

ll p[65],k,x,cnt,f[65];

int T,n,q;

void insert(ll x)

{

   per(i,63,0)

   {

      if(!((x>>i) & 1)) continue;

      if(!p[i]) {p[i] = x;break;}

      x ^= p[i];

   }

}

void rebuild()

{

   rep(i,0,63)

   {

      per(j,i-1,0) if((p[i] ^ p[j]) < p[i]) p[i] ^= p[j];

      if(p[i]) f[cnt++] = p[i];

   }

}

ll calc(ll k)

{

   ll cur = 0;

   rep(i,0,cnt-1) if(k & (1ll << i)) cur ^= f[i];

   return cur;

}

int main()

{

   scanf("%d",&n);

   rep(i,1,n) scanf("%lld",&x),insert(x);

   rebuild();

   scanf("%d",&q);

   while(q--)

   {

      scanf("%lld",&k);

      if(cnt != n) k--;

      if(k >= (1ll<<cnt)) printf("-1\n");

      else printf("%lld\n",calc(k));

   }

   return 0;

}