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

题意

给定长度为 $n$ 的数组，有 $q$ 次查询，每次查询由数组的子集所异或出结果的第 $k$ 小值是多少。

思路

将数组所有元素插入线性基中，然后对其进行 rebuild 操作：从高位往低位开始枚举，对于每一个 $i$ ，枚举 $j

需要注意的是由线性基所异或出的结果都是非零的，而查询的第 $k$ 小异或值可能为零，于是我们需要在构造线性基的时候判断当前这些数能否异或出 $0$ ，再对最终所要查询的结果进行特判即可。

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;
}