题目传送门：Problem - 3949 (hdu.edu.cn)

题意 / Problem

给定一个长度为N的数组a（0 <= ai <= 1e18），问这N个数字能够异或出的结果组成的集合中第k小的数字。

思路 / Thought

线性基模板题。

最近在学习线性基，所以做了一道关于线性基的例题。

关于线性基的基础可以看这个《[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记》

代码 / Code

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXL = 63, maxn = 80;
int p[maxn], d[maxn], tot, N, M;

void ins(int x)
{
	for(int i = MAXL;i >= 0; -- i)//remember to Traverse from back to front
	{
		if(!x)return;//special judge
		if(!(x >> i & 1))continue;
		
		if(p[i])x ^= p[i];
		else return p[i] = x, void();
	}
}

void rebuild()
{
	tot = 0;
	for(int i = 0;i <= MAXL; ++ i)//renew the p[i] by p[j], and j < i
	{
		for(int j = 0;j < i; ++ j)if(p[i] >> j & 1)p[i] ^= p[j];
		if(p[i])d[tot ++] = p[i];//save the p to d
	}
}

int que_min(int k)
{
	k -= (tot != N);
	if((k >> tot) >= 1)return -1;//beyond the border, please remember to add LL
	int res = 0;
	for(int i = 0;i < tot; ++ i)if(k >> i & 1)res ^= d[i];
	return res;
}

void solve()
{
	cin >> N;// N is the length of array
	memset(p, 0, sizeof p);// this step is important
	for(int i = 1;i <= N; ++ i)
	{
		int x;cin >> x;
		ins(x);// insert x into the Linear Basis	
	}
	rebuild();// do not forget to reBuild the Linear Basis
	
	cin >> M;// M is the count of queries
	
	while(M --)
	{
		int k;cin >> k;// to get the Kth small element in the XOR array
		cout << que_min(k) << '\n'; 
	}
	
}

signed main()
{
	ios::sync_with_stdio(0);
	int _;cin >> _;
	for(int i = 1;i <= _; ++ i)
	{
		cout << "Case #" << i << ":\n";
		solve();//output the answer
	}
	return 0;
}