嘟嘟嘟
集训的时候发现自己不会线性基，就打算学一下。
这东西学了挺长时间，其实不是因为难，而是天天上午考试，下午讲题，结果晚上就开始颓了。
今天总算是有大块的时间好好学了一遍。
这里推荐menci大佬的博客：线性基学习笔记
这道题就是求一个集合的第\(k\)小亦或和。
首先线性基的概念、构造方法什么的看上面的blog就好啦。
这里补充一点，只有求第\(k\)小（大）的亦或和的时候才用把每一位独立开来，即必须满足\(p[i] = 2 ^ｉ\)。其他的操作（比如亦或最大值）就不用了。
那么现在我们已经得到了线性基，且满足如果\(p[i]\)存在，就有\(p[i] = 2 ^ i\)。
首先，对于不存在的\(p[i]\)，要把他踢出去，因为这一位在计算答案的时候是没有贡献的。
然后如果求第\(k\)小，就把\(p[i]\)从低位到高位存到另一个数组中（去0位）；如果是第\(k\)大，就应该从高位到低位存下来。
那么对于\(k\)，转换成二进制，如果第\(i\)位为\(0\)，就把答案亦或上\(p[i]\)。
大体的流程就是这样。
接下来说一下细节：
1.如果线性基大小小于\(n\)，就说明有的数能被其他数亦或得到，也就是说，答案是包含\(0\)的。这时候就要把\(k\)减1。
2.无解条件是\(k > 2＾cnt - 1\)。之所以减1，是因为虽然有\(2 ^ cnt\)种可能，但是0是不算的，因此只有\(2 ＾cnt - 1\)个数。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxN = 63;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m;
ll p[maxN + 5];
In void insert(ll x)
{
for(int i = maxN; i >= 0; --i)
{
if((x >> (ll)i) & 1)
{
if(p[i]) x ^= p[i];
else
{
for(int j = i - 1; j >= 0; --j) if((x >> j) & 1) x ^= p[j];
for(int j = maxN; j > i; --j) if((p[j] >> i) & 1) p[j] ^= x;
p[i] = x; return;
}
}
}
}
ll b[maxN + 5], cnt = 0;
In void change() //第k小，正着存
{
for(int i = 0; i <= maxN; ++i) if(p[i]) b[cnt++] = p[i];
}
In ll query(ll k)
{
if(cnt < n) --k;
if(k > (1LL << cnt) - 1) return -1;
ll ret = 0;
for(int i = 0; i < cnt; ++i)
{
if((k >> i) & 1) ret ^= b[i];
}
return ret;
}
In void init()
{
Mem(p, 0); Mem(b, 0); cnt = 0;
}
int main()
{
int T = read(), cntT = 0;;
while(T--)
{
printf("Case #%d:\n", ++cntT);
init();
n = read(); ll x;
for(int i = 1; i <= n; ++i) x = read(), insert(x);
change();
m = read();
for(int i = 1; i <= m; ++i) x = read(), write(query(x)), enter;
}
return 0;
}