HDU 3949 XOR （线性基，模板）

Description

XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its value by check the digit of corresponding position in A and B. And for each digit, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0. And we simply write this operator as ^, like 3 ^ 1 = 2, 4 ^ 3 = 7. XOR is an amazing operator and this is a question about XOR. We can choose several numbers and do XOR operatorion to them one by one, then we get another number. For example, if we choose 2, 3 and 4, we can get 2^3^4=5. Now, you are given N numbers, and you can choose some of them(even a single number) to do XOR on them, and you can get many different numbers. Now I want you tell me which number is the K-th smallest number among them.

Input

First line of the input is a single integer T(T<=30), indicates there are T test cases.

For each test case, the first line is an integer N(1<=N<=10000), the number of numbers below. The second line contains N integers (each number is between 1 and 10^18). The third line is a number Q(1<=Q<=10000), the number of queries. The fourth line contains Q numbers(each number is between 1 and 10^18) K1,K2,……KQ.

Output

For each test case,first output Case #C: in a single line,C means the number of the test case which is from 1 to T. Then for each query, you should output a single line contains the Ki-th smallest number in them, if there are less than Ki different numbers, output -1.

Sample Input

2
2
1 2
4
1 2 3 4
3
1 2 3
5
1 2 3 4 5


Sample Output

Case #1:
1
2
3
-1
Case #2:
0
1
2
3
-1


AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, q;

class LinearBase {
public:
const static int maxn = 64 - 1;
LL d[maxn], p[maxn], tot;
void clear() {
tot = 0;
memset(d, 0, sizeof(d));
memset(p, 0, sizeof(p));
}

bool insert(LL val) {
for (int i = maxn - 1; i >= 0; i--) {
if ((val >> i) & 1) {
if (!d[i]) {
d[i] = val;
break;
} else {
val ^= d[i];
}
}
}
return val > 0;
}

LL query_max(LL def = 0) {
LL res = def;
for (int i = maxn - 1; i >= 0; i--) {
res = max(res, res ^ d[i]);
}
return res;
}

LL query_min() {
for (int i = 0; i < maxn; i++) {
if (d[i])
return d[i];
}
return 0;
}

void rebuild() {
memset(p, 0, sizeof(p));
tot = 0;
for (int i = maxn - 1; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if ((d[i] >> j) & 1) {
d[i] ^= d[j];
}
}
}
for (int i = 0; i < maxn; i++) {
if (d[i]) {
p[tot++] = d[i];
}
}
}

LL query_kth(LL k) {
if (k >= 1LL << tot) {
return -1;
}
LL res = 0;
for (int i = 0; i < maxn; i++) {
if ((k >> i) & 1) {
res ^= p[i];
}
}
return res;
}

} lb;

int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
IO;
#endif // LOCAL_IM0QIANQIAN

int T;
cin >> T;
for (int ti = 1; ti <= T; ti++) {
bool flag = true;
lb.clear();
cin >> n;
for (int i = 0; i < n; i++) {
LL x;
cin >> x;
flag &= lb.insert(x);
}
cout << "Case #" << ti << ":" << endl;
cin >> q;
lb.rebuild();
for (int i = 0; i < q; i++) {
LL x;
cin >> x;
cout << lb.query_kth(x - 1 + flag) << endl;
}
}
return 0;
}