HDU 3949 XOR （线性基，模板）

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

221 241 2 3 431 2 351 2 3 4 5

Sample Output

Case #1:123-1Case #2:0123-1

题意

给定长度为 n n 的数组，有 qq 次查询，每次查询由数组的子集所异或出结果的第 k k

思路

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

操作结束以后，对于 d[i] d [ i ] 来说只有 i i 这一位为 11 ，其余位都为 0 0 ，我们按从小到大的顺序把其中的非零元素放入 pp

在查询第 k k 大异或值的时候，我们根据 kk 的二进制进行构造，对于 1 1 的位，便异或上相应的 p[i]p[i]

需要注意的是由线性基所异或出的结果都是非零的，而查询的第 k k 小异或值可能为零，于是我们需要在构造线性基的时候判断当前这些数能否异或出 00

AC 代码

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。