比赛时遇到这种排列构造题，最优策略是打表找规律。
题目要求 \(p_i \oplus p_{i+1} > \mid p_i-p_{i+1}\mid\)，撕烤什么时候不满足条件。由于异或是不进位加法，也是不退位减法，这里显然用后者，立即推出 \(p_i \oplus p_{i+1} \ge \mid p_i-p_{i+1}\mid\)。等号取到当且仅当 \(p_i\mid p_{i+1}=p_i\) 或者 \(p_i\mid p_{i+1}=p_{i+1}\)。
然后进行构造：构造 \(n\) 的答案可以先构造 \(n-1\) 的答案。
你会发现 \(n=3\) 的时候会寄，但是 \(n=4\) 时可以用 \(4\) 来救场，插到 \(2\) 和 \(3\) 之间，于是 \(n=4\) 时答案为 \(1,2,4,3\)。
然后 \(n=7\) 时又寄了，无可救药，因为 \(7\) 的二进制表示为 \(111\)，跟谁挨在一起都会导致不满足条件，同理 \(n=2^k-1\) 时都无解。
\(n=8\) 时又活了，可以将 \(8\) 放在 \(7\) 前面，满足条件。
于是可以大胆猜测答案是：$$1,2,4,3,5,6,8,7,9,10,12,11\cdots$$
那么又出现了一个问题： \(n=11\) 时呢?更进一步地，\(n\) 形如 \(4k+3\) 且有解时呢？这时还是有药可救的。首先 \(n\) 不能放在最后，那么与其相邻的两个数必须满足条件，且这两个数在 \(n\) 插入这两个数中间前相邻。如何求出这两个数呢？可以将 \(n\) 取反，再做一遍lowbit，得出的结果 \(x\) 一定满足条件，而 \(x+1\) 和 \(x+2\) 也满足条件且一定相邻，取这两个数即可。
综上，\(n=2^k-1\) 时无解，\(n\) 为偶数或模 \(4\) 余 \(1\) 时直接构造即可，\(n\) 形如 \(4k+3\) 时先构造 \(n-1\) 的答案，再把 \(n\) 插进去。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n,a[100005];
int lowbit(int x){x=(~x);return x&(-x);
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;if(n==1){cout<<"1\n";continue;}int x=log2(n+1);if((1<<x)==n+1){cout<<"-1\n";continue;}if(n%4==1||n%2==0){for(int i=1;i<=n;i++){if(i%4==1||i%4==2) a[i]=i;if(i%4==3) a[i]=i+1;if(i%4==0) a[i]=i-1;}for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<'\n';}if(n%4==3){int y=lowbit(n);for(int i=1;i<n;i++){if(i%4==1||i%4==2) a[i]=i;if(i%4==3) a[i]=i+1;if(i%4==0) a[i]=i-1; }for(int i=1;i<n;i++){cout<<a[i]<<' ';if(a[i]==y+1) cout<<n<<' ';}cout<<'\n';}}return 0;
}