异或运算

AcWing-210-异或运算

分析

见《进阶指南》第167页。

实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int N = 10010;
int n, q;
ULL a[N], p[N];

void insert (ULL x) {
    for (int i = 61; i >= 0; -- i) {
        if ((x >> i) & 1) {
            if (p[i] == 0) {
                p[i] = x;
                return;
            }
            x = x ^ p[i];
        }
    }
}
bool cmp (const ULL& a, const ULL& b) {
    return a > b;
}

int main () {
    int _;
    cin >> _;
    for (int T = 1; T <= _; ++ T) {
        memset(p, 0, sizeof(p));
        cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> a[i];

        for (int i = 1; i <= n; ++ i) insert(a[i]);
        int t = 0;
        for (int i = 0; i < 62; ++ i)
            if (p[i] > 0)
                ++ t;
        bool has_zero = (t < min(62, n));
        for (int i = 0; i < 62; ++ i) { // 简化阶梯形
            if (p[i] == 0) continue;
            for (int j = i + 1; j < 62; ++ j)
                if ((p[j] >> i) & 1)
                    p[j] = p[j] ^ p[i];
        }
        sort (p, p + 62, cmp);
        
        cout << "Case #" << T << ":" << endl;
        cin >> q;
        while (q --) {
            ULL k;
            cin >> k;
            if (has_zero) k = k - 1;

            if (k >= (1ULL << t)) {
                cout << -1 << endl;
            } else {
                ULL res = 0;
                for (int i = t - 1; i >= 0; -- i)
                    if ((k >> i) & 1)
                        res ^= p[t - i - 1];
                cout << res << endl;
            }
        }
    }
    return 0;
}