# 题意
给出n个数,ai,从中选取一些进行异或运算(可以只有一个),求出他们所有可能组合得到的异或值去重后的第k小的值
1 ≤ ai ≤ 1018
# 题解
因为是去重后的值所以求出线性基然后组合即可
因为1 ≤ ai ≤ 1018即所有数都在二进制64位之间,可以将每个数看做是64位二进制数,通过高斯消元后求得简化的行阶梯型矩阵,
即线性基,矩阵的秩为r,首先最大的数即所有数异或,其余的都是组合,一共有2r种,这里是包含了值为0的项,
需要判断是否存在0,因为题目中不会选出ai ^ ai 所以不一定存在0,在高斯消元后如果存在0,即说明存在几个数异或等于0
将k--即可,然后通过二进制求出第k-1小的数,如果 k >= 2t 即没有这么多不同的值就输出-1
1 #include <bits/stdc++.h> 2 #define ull long long 3 using namespace std; 4 const int N=1e4+10; 5 int n,m; 6 ull a[N]; 7 int main() { 8 int t; 9 cin >> t; 10 for (int T = 1; T <= t; T++) { 11 cin >> n; 12 for (int i = 1; i <= n; i++) 13 cin >> a[i]; 14 bool zero = 0; 15 int r = n; 16 for (int i = 1; i <= n; i++) { 17 for (int j = i + 1; j <= n; j++) 18 if (a[j] > a[i]) swap(a[i], a[j]); 19 20 if (a[i] == 0) {//最大的主元为0后面的肯定也是0 21 r = i - 1; 22 zero = 1; 23 break; 24 } 25 for (int k = 63; k >= 0; k--) 26 if (a[i] >> k & 1) { 27 for (int j = 1; j <= n; j++) 28 if (j != i && (a[j] >> k & 1)) a[j] ^= a[i]; 29 break; 30 } 31 } 32 cin >> m; 33 cout << "Case #" << T << ":" << endl; 34 while (m--) { 35 ull k, ans = 0; 36 cin >> k; 37 if (zero) k--; 38 if (k >= 1llu << r) puts("-1"); 39 else { 40 for (int i = r-1 ; i >= 0; i--) 41 if (k >> i & 1) ans ^= a[r - i]; 42 cout << ans << endl; 43 } 44 } 45 } 46 }