题意：给定集合，求一个最大的x，使得存在一个0 ~ 2^x - 1的排列，满足每相邻的两个数的异或值都在S中出现过。Si <= 2e5

解：若有a，b，c，令S1 = a ^ b, S2 = b ^ c，则有a ^ c = S1 ^ S2

因为有0存在，所以每个数都能表示成它到0路径上的所有间隔的异或和，也就是每个数都能被表示出来。我们用线性基来判断。

找到最大的x之后，我们可以发现，线性基中x个数的2^x种选法一一对应这2^x个数。于是直接采用格雷码来找这个排列，每加一位，就在x个数中添加 / 删除一个数到异或集合中。

我的实现较复杂。实际上只要把线性基这x个数记下来，格雷码的时候选择是否异或即可。

1 #include 
      
        2  3 const int N = 500010; 4  5 int n, a[N], base[64], T, id[64], sta[N], pos[N], s; 6  7 inline void clear() { 8     memset(base, 0, sizeof(base)); 9     memset(id, 0, sizeof(id));10     return;11 }12 13 inline void insert(int x, int v) {14     int V = 0;15     for(int i = T - 1; i >= 0; i--) {16         if(!((x >> i) & 1)) {17             continue;18         }19         if(base[i]) {20             x ^= base[i];21             V ^= id[i];22         }23         else {24             base[i] = x;25             id[i] = V | (1 << i);26             break;27         }28     }29     return;30 }31 32 inline bool check() {33     for(int i = T - 1; i >= 0; i--) {34         if(!base[i]) {35             return false;36         }37     }38     return true;39 }40 41 inline void find(int x) {42     int t = x;43     for(int i = T - 1; i >= 0; i--) {44         if(!((x >> i) & 1)) {45             continue;46         }47         x ^= base[i];48         sta[t] ^= id[i];49     }50     return;51 }52 53 void DFS(int k) {54     if(k == -1) {55         printf("%d ", pos[s]);56         return;57     }58     DFS(k - 1);59     s ^= 1 << k;60     DFS(k - 1);61     return;62 }63 64 int main() {65     scanf("%d", &n);66     for(int i = 1; i <= n; i++) {67         scanf("%d", &a[i]);68     }69     std::sort(a + 1, a + n + 1);70     int fin = 0;71     for(T = 0; T <= 18; T++) {72         int lm = (1 << T) - 1;73         clear();74         for(int i = 1; i <= n && a[i] <= lm; i++) {75             insert(a[i], i);76         }77         if(check()) {78             fin = T;79         }80     }81     T = fin;82     /// T 83     int lm = (1 << T) - 1;84     for(int i = 1; i <= lm; i++) {85         find(i);86         pos[sta[i]] = i;87     }88     printf("%d\n", T);89     DFS(T - 1);90     puts("");91     return 0;92 }