题目大意

给出一个集合 SS，构造一个排列 aa，其长度为 2x2^x，要求 ∀i,ai∈[0,2x−1]\forall i,a_i\in [0,2^x-1] 且 ai⊕ai+1∈Sa_i\oplus a_{i+1}\in S，在满足这个条件的情况下要求 xx 尽量大。

思路

这个题我们分成两部分来做，即如何求出 xx 和如何构造这个序列。

Part 1

首先根据题目可以看出，任意一个合法的 xx，它应该满足对于所有 ai∈[0,2x−1]a_i\in [0,2^x-1]，我们可以用 SS 中的任意多个数异或起来得到 axa_x。

为什么呢，这样想，对于长度为 2x2^x 的排列 aa，里面总有一个数为 00，由于相邻两个数的异或值是 SS 中的一个数，所以与这个 00 相邻的两个数都是 SS 中的数，而与这两个数相邻的两个数都能被表示为 SS 中的两个数异或起来，以此类推，最终可以得知所有的数都可以被表示为 SS 中任意多个数异或起来。

我们知道，SS 中任意多个数相互异或所得到的数一定也能被表示为 SS 的线性基中任意多个数相互异或所得到的数，所以这个排列中的所有数一定也能被表示为 SS 的线性基中任意多个数异或起来，由于线性基的性质，线性基中不同的异或组合异或出的数都是不一样的，所以这个线性基一定能异或出正好 2x2^x 个数，也就是 00 到 2x−12^x-1 这些数。

说了这么多，我们如何确定最大的 xx 使得排列 aa 一定存在呢？很简单，我们直接求出 SS 的线性基，然后看第一个为 00 的 baseibase_i 是第几个就行了，由于存在这样一个为 00 的 baseibase_i，就会导致某些最高位为 ii 的数没法异或出来，所以这个 ii 一定就是最大的 xx。

但有一个问题，我们看这样一组数据：

1
2
2
4 5

不难求出，这个 SS 的线性基为{1,4}\{1,4\}，这样的话第一个为 00 的 baseibase_i 就是 base1base_1 了，所以我们的程序就会误认为 xx 应该取 11，但显然这样是不合法的。

这个 bug 出现的主要原因在于我们可以通过把较高位异或掉来异或出一个最高位较低的数，但显然我们想要的并不是这样的，因为我们并不能通过异或把两个数的最高位变高，那么怎么解决呢。

很简单，我们在插入时枚举一下 xx，只插入那些小于 2x2^x 的数就行了，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int x)
{
	int t = x;
	for(int i = 20; i >= 0; i--)
		if((x>>i)&1)
			if(!bas[i])
			{
				bas[i] = x;
				a[++k] = t;//这里的 a 数组在 part 2 里面会有用，k 可以理解为是统计有多少个 base 不为 0
				break;
			}
			else
				x ^= bas[i];
}
1
2
3
4
5
6
7
8
sort(s+1, s+1+n);
for(int i = 0, j = 1; i <= 20 && j <= n; i++)
{
    while(s[j] < (1<<i) && j <= n)
        insert(s[j++]);
    if(k == i)
        m = i;
}

Part 2

很多大佬都说这一部分很简单，所以讲得不太详细，但由于我比较菜，所以我觉得这里才是最难的部分。

构造 aa 的方法很多，一种方法是用格雷码来构造，然而采用这类方法的大佬大多没有给出这样做的原因，还有一种是用遍历一棵二叉树的方法，我这里采用较为暴力的办法，即直接 DFS。

在 Part 1 的代码里面，我们用一个 a 数组存了插入线性基的数，而这些数正是我们相邻两个数异或起来所得到的值的集合（也就是说我们把构造出来的排列中相邻两个数异或一下，只能得到这些数），当然不这样构造应该也是可以的，这只是我们构造出来的排列的一个性质罢了，因为如果一个数没有被插入到线性基中，那只有可能是它能被其他的数异或出来，所以我们只需要这些数就能异或出 2x2^x 个数了。

参考代码

1
2
3
4
5
6
7
8
9
10
void dfs(int x, int num)
{
	printf("%d ", num);
	if(x == (1<<m))
		exit(0);
	vis[num] = 1;
	for(int i = 1; i <= k; i++)
		if(!vis[num^a[i]])
			dfs(x+1, num^a[i]);
}

这样看起来很不靠谱，理论上来说应该是 O(nlog⁡M)O(n^{\log M}) 的，但实际上，由于这 xx 个数可以肯定能正好异或出这 2x2^x 个数，所以应该不存在回溯的情况，也就是说，这个算法的时间复杂度实际上是 O(nlog⁡M)O(n\log M) 的，并且经过 CF 的实际验证，这样确实不会回溯。

因此，这个算法的总时间复杂度为 O(nlog⁡n+nlog⁡M+nlog⁡M)O(n\log n+n\log M+n\log M)。

参考代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
namespace IO
{
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define isdigit(c) (c>=48&&c<=57)
	#define isalpha(c) ((c>=65&&c<=90)||(c>=97&&c<=122))
	template<typename T> inline void read(T &x)
	{
		x=0;
		register int f=1;
		register char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
const int N = 2e5+10, inf = 0x3f3f3f3f;
int n, m, k, s[N], vis[N*10], bas[20], a[20];
void insert(int x)
{
	int t = x;
	for(int i = 20; i >= 0; i--)
		if((x>>i)&1)
			if(!bas[i])
			{
				bas[i] = x;
				a[++k] = t;
				break;
			}
			else
				x ^= bas[i];
}
void dfs(int x, int num)
{
	printf("%d ", num);
	if(x == (1<<m))
		exit(0);
	vis[num] = 1;
	for(int i = 1; i <= k; i++)
		if(!vis[num^a[i]])
			dfs(x+1, num^a[i]);
}
int main()
{
	read(n);
	for(int i = 1; i <= n; i++)
		read(s[i]);
	sort(s+1, s+1+n);
	for(int i = 0, j = 1; i <= 20 && j <= n; i++)
	{
		while(s[j] < (1<<i) && j <= n)
			insert(s[j++]);
		if(k == i)
			m = i;
	}
	printf("%d\n", m);
	k = 0;
	memset(bas, 0, sizeof(bas));
	for(int i = 1; i <= n; i++)
		if(s[i] < (1<<m))
			insert(s[i]);
	dfs(1, 0);
	return 0;
}

格雷码的那种思路是真心看不懂，也没有一个大佬做出详细的解释，遍历二叉树的思路还比较好懂，并且常数也比我这个小，但个人觉得我这个方法还要好懂一点（（（