给由 $n$ 个数组成的一个可重集 $S$ ，每次给定一个数 $k$ ，求一个集合 $T⊆S$ ，使得集合 $T$ 在 $S$ 的所有非空子集的不同的异或和中，其异或和 $T_1\ \text{xor}\ T_2\ \text{xor}\ …\ \text{xor}\ T_{|T|}$ 是第 $k$ 小的。求这个第 $k$ 小的异或和。
题解
线性基+特判
板子题没什么好说的，直接求出严格线性基，由于每个最高位只有一个因此按位判断即可。
关键在于一个特判：原来的可重集可能能够组成0，也可能不能够组成0，需要判断一下0是否算在内。
时间复杂度 $O(n\log n)$
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[100010] , tot;
int main()
{
int n , m , i , flag = 0;
ll j , ans;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%lld" , &a[i]);
if(a[i] == 0) flag = 1;
}
for(j = 1ll << 49 ; j ; j >>= 1)
{
for(i = tot + 1 ; i <= n ; i ++ )
if(a[i] & j)
break;
if(i > n) continue;
swap(a[i] , a[++tot]);
for(i = 1 ; i <= n ; i ++ )
if(i != tot && a[i] & j)
a[i] ^= a[tot];
}
for(i = 1 ; i <= n ; i ++ )
if(a[i] == 0)
flag = 1;
scanf("%d" , &m);
while(m -- )
{
scanf("%lld" , &j) , j -= flag;
if(j >= 1ll << tot) puts("-1");
else
{
ans = 0;
for(i = 1 ; i <= tot ; i ++ )
if(j & (1ll << (tot - i)))
ans ^= a[i];
printf("%lld\n" , ans);
}
}
return 0;
}