k大异或和（线性基）

前置知识：线性基

题目

给出一个由$n$个数组成的可重集合$S$，每次给出一个数$k$，求一个集合$T\subseteq S$，使得集合$T$在$S$的所有非空子集的不同的异或和中，其异或和$T_1\oplus T_2\oplus \cdots \oplus T_{|T|}$是第$k$小的。

$1\le n,m\le 10^5,0\le S\le 2^{50}$

题解

构造$S$的线性基$d$，则$S$的所有非空子集的不同异或和都可以由$d$中若干个数的异或和得到且一一对应。我们可以对线性基进行一些操作，使得$d$在满足$d_i$的最高位为$i+1$的情况下数组$d$单调递增。去掉$d_i$为空的部分，假设余下的部分长度为$cnt$，答案为$ans$，$ans$初始为$0$。

• 若$k>2^{cnt}-1$，显然不存在
• 若$k\le 2^{cnt}-1$，则对于所有$i\in [1,cnt]$，若$k$的第$i$位为$1$，则$ans=ans\oplus d_i$

注意在构造线性基的时候要顺便特判有没有若干个数异或值为$0$，有的话$k$要减一。

code

#include
using namespace std;
int n,m,vt,fl,d1=0;
long long ans=0,k,a[100005],d[55];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		fl=0;
		for(int j=50;j>=0;j--){
			if(a[i]&(1ll<<j)){
				if(!d[j]){
					d[j]=a[i];fl=1;
					break;
				}
				a[i]^=d[j];
			}
		}
		if(!fl) vt=1;
	}
	for(int i=50;i>=0;i--){
		for(int j=i-1;j>=0;j--){
			if(d[i]&(1ll<<j)) d[i]^=d[j];
		}
	}
	for(int i=0;i<=50;i++){
		if(d[i]) d[d1++]=d[i];
	}
	scanf("%d",&m);
	while(m--){
		scanf("%lld",&k);
		k-=vt;
		if(k>(1ll<<d1)-1){
			printf("-1\n");continue;
		}
		ans=0;
		for(int i=0;i<d1;i++){
			if(k&(1ll<<i)) ans^=d[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46