跳转至

HDU3949 XOR

题意

给定 n(n \le 10000) 个数 a_1, a_2, \ldots, a_n，以及 Q(Q\le 10000) 个询问，每次询问这些数（至少一个，不能不选）能够组成的异或和中第 k 小的数是什么（去掉重复的异或和）。

题解

学习线性基时做的一道入门例题。首先将这些数异或的向量空间的一组线性基\mathfrak{B}求出来，然后判断能否取零，也就是在求线性基时是否存在向量可以被前面的向量张成，如果可以取零，那么可取的数的数量可以多一，相当于k–-，接着考虑如何求第k大的数，假设我们现在将线性基中不为零的数提取出来，会发现其实这个的运算大小也是与二进制类似的，因为异或没有进位，所以如果将线性基中的数按照大小排序为(v1,v2,\cdots ,v_m)的话取10000得到的结果肯定比取0xxxx得到的结果要大，这里的取什么指是否取线性基中这一位上的向量。

于是将k转化成二进制(x_0,x_1,x_2.\cdots x_m)答案就是XOR_{i=0}^{63} v_i\cdot x_i

程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MAX_N 10007
#define reg register
typedef long long ll;

int N, Q, top;
ll a[MAX_N], b[64], c[64], tot;
bool has;

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-') y = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

inline ll quick_pow (ll x, ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans *= x;
        p >>= 1;
        x *= x;
    }
    return ans;
}

inline void init () {
    memset(b, 0, sizeof(b));
    for (int i = 1;i <= N; ++i) {
        for (int j = 63; j >= 0; --j) {
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k)
                        if (b[k] && b[j] >> k & 1)
                            b[j] ^= b[k];
                    for (int k = j + 1; k <= 63; ++k)
                        if (b[k] >> j & 1)
                            b[k] ^= b[j];
                    break;
                }
            }
        }
        if (a[i] == 0) has = true;
    }
    top = 0;
    for (int i = 0;i <= 63; ++i)
        if (b[i])
            c[++top] = b[i];
    tot = quick_pow(2, top);
}

inline ll solve (ll x) {
    ll res = 0;
    if (has) x--;
    if (x >= tot) return -1;
    int cnt = 0;
    while (x) {
        cnt++;
        res ^= ((x & 1) * c[cnt]);
        x >>= 1;
    }
    return res;
}

int main () {
    int T, cnt = 0;
    read(T);
    while (T--) {
        read(N);
        for (int i = 1;i <= N; ++i) read(a[i]);
        has = false;
        init();
        read(Q);
        ll x;
        printf("Case #%d:\n", ++cnt);
        while (Q--) {
            read(x);
            printf("%lld\n", solve(x));
        }
    }
    return 0;
}