题目来源：Codeforces Round #558 (Div. 2) CF1163E Magical Permutation
算法：线性基
题目大意
给定一个，含有(n)个互不相同正整数的集合(S)。
我们称一个排列是合法的，当且仅当同时满足如下两个条件：
- 这是一个(0,1,dots ,2^x-1)的排列，其中(x)是一个非负整数。
- 排列里，任意相邻两数的异或值，都出现在(S)中。
请求出，最长的合法排列。换句话说，请你找到一个最大的(x)，并构造出一个长度为(2^x)的合法排列。
数据范围：(1leq nleq 2 imes 10^5)，(S)集合里的数(leq2 imes 10^5)。
本题题解
设(S)里最大的数为(M)。
如果排列的二进制下最高位，超过了(S)里最大的数（即(2^{x-1}>M)），那么这样的排列一定是不合法的。因为最高位一定会出现在异或值中，但它无法被(S)里的数表示出来。因此，满足条件的(x)不超过(log_2M+1)。于是我们考虑枚举所有(x)，判断它是否可行。
引理：一个(x)可行当且仅当，(0,1,dots,2^x-1)都能被表示为(S)的一个子集的异或和。
证明-必要性：
考虑一个合法的排列，(p_0,p_1,dots ,p_{2^x-1})，设(p_t=0)。
首先，(p_t)就是一个空集的异或和，所以对(p_t)显然满足条件。
因为排列合法，所以在(p_{t+1},p_{t+2},dots ,p_{2^x-1})中，每个数和它前面一个数的异或值，都属于(S)。具体来说，设(c_i=p_{i-1}operatorname{xor}p_{i})，则(forall i>t:c_iin S)，因此(p_{t+1},p_{t+2},dots ,p_{2^x-1})都能被表示为一段连续的(c_i)的异或和，也就是(S)里若干个数的异或和。
类似地，在(p_{t-1},p_{t-2},dots,p_0)中，每个数和它后面一个数的异或值，都属于(S)。设(d_i=p_{i}operatorname{xor}p_{i+1})，则(forall i<t:d_iin S)，因此(p_{t-1},p_{t-2},dots,p_0)都能被表示为一段连续的(d_i)的异或和，也就是(S)里若干个数的异或和。
由此就证明了：【(0,1,dots,2^x-1)都能被表示为(S)的一个子集的异或和】是一个长度为(2^x)的排列合法的必要条件。枚举(x)后，我们可以通过对(S)建线性基，看线性基前(x)位是否填满，来检查(x)是否满足这个必要条件。
接下来要证明充分性，相当于把这个排列构造出来。也正是题目要我们做的事情。
现在我们知道，(0,1,dots,2^x-1)都能被表示为(S)的一个子集的异或和。根据线性基的理论，对(S)建线性基后，(S)的每个子集，都对应线性基的一个子集，它们异或和相等。所以(0,1,dots,2^x-1)每个数，都能被表示为：【(S)里，用来建线性基的，这(x)个数】的一个子集。并且每个数对应的子集互不相同：用来建线性基的有(x)个数，正好形成(2^x)个子集，和每个值一一对应。
通过线性基，我们能求出，每个值对应了哪个子集。前面说了，这些子集互不相同。于是把它们用二进制表示为(0,1,dots,2^x-1)。
那么问题转化为，把(0,1,dots,2^x-1)（所有子集）重新排列，使得任意相邻两个数，只有一位二进制为不同。这就是格雷码的定义，可以采用「CSP-S 2019」格雷码这题题面里介绍的构造方法。
时间复杂度(O(nlog n+nlog M+M))。
参考代码：
//problem:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=2e5,LOG=18;
int n;
uint s[MAXN+5];
uint mask_to_val[MAXN+5];
struct LinerBase{
int size;
uint base[MAXN+5],mask[MAXN+5],val[MAXN+5];
void insert(const uint& v){
uint t=v;
uint ma=0;
for(int i=LOG;i>=0;--i) if((t>>i)&1) {
if(!base[i]){
base[i]=t;
++size;
ma|=(1<<(size-1));
mask[i]=ma;
val[size]=v;
return;
}
else{
t^=base[i];
ma^=mask[i];
}
}
}
uint query_mask(const uint& v){
uint t=v;
uint ma=0;
for(int i=LOG;i>=0;--i) if((t>>i)&1) {
assert(base[i]);
t^=base[i];
ma^=mask[i];
}
return ma;
}
}B;
vector<uint> get_gray(uint x){
if(x==0){
vector<uint> res(1,0);
return res;
}
vector<uint> res=get_gray(x-1);
uint len=(1u<<(x-1));
for(uint i=0;i<len;++i){
res.push_back(res[len-1-i] | (1u<<(x-1)));
}
return res;
}
int main() {
cin>>n;
for(int i=1;i<=n;++i){
cin>>s[i];
}
sort(s+1,s+n+1);
int j=0;
int x=-1;
for(int i=0;i<=LOG;++i){
while(j+1<=n && s[j+1]<(1u << i)){
++j;
B.insert(s[j]);
}
if(B.size==i) x=i;
}
assert(x!=-1);
for(uint i=0;i<(1u<<x);++i){
mask_to_val[B.query_mask(i)]=i;
}
// cerr<<x<<endl;
// for(uint i=0;i<(1u<<x);++i)
// cerr<<mask_to_val[i]<<" ";
// cerr<<endl;
vector<uint> v=get_gray(x);
cout<<x<<endl;
for(uint i=0;i<(1u<<x);++i){
cout<<mask_to_val[v[i]]<<" ";
}
cout<<endl;
return 0;
}