题目链接

210. 异或运算

给定你由 \(N\) 个整数构成的整数序列，你可以从中选取一些（至少一个）进行异或（\(\operatorname{xor}\)）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第 \(k\) 小的结果是多少。

输入格式

第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。

对于每组测试数据，第一行包含整数 \(N\)。

第二行包含 \(N\) 个整数(均在 \(1\) 至 \(10^{18}\) 之间)，表示完整的整数序列。

第三行包含整数 \(Q\)，表示询问的次数。

第四行包含 \(Q\) 个整数 \(k_1,k_2,…,k_Q\)，表示 \(Q\) 个询问对应的 \(k\)。

输出格式

对于每组测试数据，第一行输出 Case #C:，其中 \(C\) 为顺序编号（从 \(1\) 开始）。

接下来 \(Q\) 行描述 \(Q\) 次询问的结果，每行输出一个整数，表示第 \(i\) 次询问中第 \(k_i\) 小的结果。

如果能得到的不同结果的总数少于 \(k_i\)，则输出 \(-1\)。

数据范围

\(1 \le N,Q \le 10000\),

\(1 \le k\_i \le 10^{18}\)

输入样例：

2
2
1 2
4
1 2 3 4
3
1 2 3
5
1 2 3 4 5


输出样例：

Case #1:
1
2
3
-1
Case #2:
0
1
2
3
-1


注意:只选取一个数字进行运算，则结果为该数字本身。

解题思路

线性基

由于线性基表示的空间和原向量组表示的空间等价，所以可以先求出线性基，用线性基来表示第 \(k\) 小数，由于线性基中每一个最高位的元素仅有一个，可以将每一个线性基元素当作一位，求第 \(k\) 小数即将 \(k\) 的二进制数表示出来相应乘以线性基元素，另外由于线性基不能表示 \(0\)，所以需要判断原向量组是否线性相关或无关，如果向量组的秩 \(k

• 时间复杂度：\(O(63n)\)

代码

// Problem: 异或运算
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/212/
// Memory Limit: 32 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair PII;
typedef pair PLL;

template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s <'0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=10005;
int t,n,k,q;
LL x,a[N];
int main()
{
scanf("%d",&t);
for(int T=1;T<=t;T++)
{
printf("Case #%d:\n",T);
scanf("%d",&n);
for(int i=0;i k=0;
for(int i=62;i>=0;i--)
{
for(int j=k;j if(a[j]>>i&1)
{
swap(a[k],a[j]);
break;
}
if(!(a[k]>>i&1))continue;
for(int j=0;j if(j!=k&&(a[j]>>i&1))a[j]^=a[k];
k++;
if(k==n)break;
}
reverse(a,a+k);
bool f=k scanf("%d",&q);
while(q--)
{
scanf("%lld",&x);
x-=f;
if(x>=(1ll< {
puts("-1");
continue;
}
LL res=0;
for(int i=0;i if(x>>i&1)res^=a[i];
printf("%lld\n",res);
}
}
return 0;
}