很牛很好的题，但不知道为什么 qoj 这么多踩。
原题/原题
简介题面：
问题 A：构造两个长度为 \(n\) 的包含 \(0\sim n-1\) 的排列 \(p,q\)，使得 \(r=p\oplus q\) 也是个排列。
首先特判 \(n=1\)。然后发现 \(\oplus_{i=0}^{n-1} r_i=\oplus_{i=0}^{n-1} q_i\oplus_{i=0}^{n-1}q_i=0\)，即 \(\oplus_{i=0}^{n-1} i=0\)，明显只有 \(n\bmod 4=0\) 时成立。
简化问题，\(p_i=i\)，那么只用构造 \(q\) 即可。
考虑已经求得另一个问题：
问题 B：\(p,q\) 都为长度为 \(2n\) 的双排列（\(0\le i<n\) 出现两次），\(r=p\oplus q\) 也是双排列。
用这个问题的答案构造原本问题的答案。例如：
把 \(n\) 复制到 \(2n\)。
将 \(p,q\) 都乘 \(4\)，\(p\) 加上 \([0,1,2,3,0,1,\ldots]\)，\(q\) 加上 \([0,2,1,3,0,2,\ldots]\)。
考虑 \(2i\) 和 \(2i+1\) 分一组，发现 \(r\) 重复的都是一组一组的，即 \(\{r_{2i}, r_{2i+1}\}=\{r_{2j},r_{2j+1}\}\)，发现只要交换 \(r_{2i}\) 和 \(r_{2i+1}\) 就可以改变情况，不交换的话 \(\{r_{2i}\bmod 4, r_{2i+1}\bmod 4\}=\{0,3\}\)，交换完之后变成 \(\{0,2\}\)。
另外问题 \(B\) 中的 \(q_x=q_y=i\) 中 \(x,y\) 的奇偶性不应相同，后面构造出的可以发现是不相同的，所以不用考虑。因为奇偶性相同的话在后面的构造会使得 \(q\) 有相同的数。
现在已经可以从 \(B\) 到 \(A\) 了，考虑求 \(B\)，实际上问题 \(B\) 可以化解成：
问题 C：构造两个排列 \(a,b\)，使得 \(a_i\oplus i,b_i\oplus i\) 使个双排列。
然后 \(p_{2i}=a_i,p_{2i+1}=b_i\)，这样就舍得 \(x,y\) 奇偶性不同了。
再求一个新问题：
问题 D：构造两个长度为 \(2^l\) 的排列 \(c,d\)，满足 \(c_i\oplus i,d_i\oplus i\) 是个双排列，并且满足 \(\{c_0,c_1,\ldots,c_{k-1}\}=\{0,1,\ldots,k-1\}\)。
- 若 \(l=0\)：\(c=\{0\},d=\{0\}\)。
- 若 \(l=1\)：\(c=\{0,1\},d=\{1,0\}\)。
先直接设 \(d_i\oplus i=2^{l-1}+\lfloor \frac{i}{2} \rfloor\)，可以发现构造出的 \(d\) 是个排列，并且对于 \(2^{l-1}\le i<2^l\) 的 \(i\) 都产生了 \(2\) 个。求得 \(c',d'\) 为当长度为 \(2^{l-1}\) 并且 \(k'=k\bmod 2^{l-1}\)时的答案：
- 若 \(k<2^{l-1}\)：\(c=c'+(d'\oplus 2^{l-1})\)。
- 否则：\(c=d'+(c'\oplus 2^{l-1})\)。
这样 D 就解决，考虑回 C，同样递归处理，对于 \(n\le 2\) 的和 D 返回一样的。考虑将 \(n\) 分解成 \(n=2^l+k\)，且 \(k<2^l\)，求得 \(c,d\) 为长度为 \(2^l\) 时问题 D 的答案，\(a',b'\) 为长度为 \(k\) 时问题 C 的答案。考虑构造：
- \(a\)
- \(b\)
首先 \(b'=c_{0\sim k-1}\)，归纳法，发现考虑 \(b\) 和 \(c_{0\sim k-1}\) 的构造方式其实是一样的，手玩一下就行。
\(\oplus i\) 后结果大于等于 \(2^l\) 的有 \(a'\) 和 \(c_{0\sim k-1}\)，因为 \(b'=c_{0\sim k-1}\)，那么刚好使得 \(2^l\le i<n\) 刚好出现两次。
小于 \(2^l\) 的有 \(c_{k\sim 2^l-1}\) 和 \(d\) 和 \(b'\)，同样 \(b'=c_{0\sim k-1}\)，回归到了问题 D，满足情况。
所以这个构造是成立的。
#include<bits/stdc++.h>
using namespace std;
int n;
void d(int p[], int q[], int n, int k)
{if(!n)return;if(n == 1){p[0] = q[0] = 0;return;}if(n == 2){q[1] = p[0] = 0;q[0] = p[1] = 1;return;}int a[n / 2], b[n / 2];d(a, b, n / 2, k % (n / 2));if(k < n / 2){for(int i = 0; i < n / 2; i++)p[i] = a[i];for(int i = n / 2; i < n; i++)p[i] = b[i - n / 2] + n / 2;}else{for(int i = 0; i < n / 2; i++)p[i] = b[i];for(int i = n / 2; i < n; i++)p[i] = a[i - n / 2] + n / 2;}for(int i = 0; i < n; i++)q[i] = (n / 2 + i / 2) ^ i;
}
void c(int p[], int q[], int n)
{if(!n)return;if(n == 1){p[0] = q[0] = 0;return;}if(n == 2){q[1] = p[0] = 0;q[0] = p[1] = 1;return;}int w = 1;while(2 * w <= n)w *= 2;int k = n - w;int h[w];c(p, q + w, k);d(h, q, w, k);for(int i = 0; i < k; i++)p[i + w] = h[i];for(int i = k; i < w; i++)p[i] = h[i];for(int i = 0; i < k; i++)p[i] += w;for(int i = w; i < n; i++)q[i] += w;
}
void pri(int x)
{printf("%d ", x);
}
void slove()
{scanf("%d", &n);if(n == 1){printf("Yes\n0\n0\n");return;}if(n&3){printf("No\n");return;}int m = n / 4;int p[m], q[m], vis[n];c(p, q, m);for(int i = 0; i < n; i++)vis[i] = 0;printf("Yes\n");for(int i = 0; i < n; i++)printf("%d ", i);printf("\n");for(int i = 0; i < m; i++){if(vis[i^p[i]]){pri(p[i]*4+2);pri(p[i]*4);}else{pri(p[i]*4);pri(p[i]*4+2);vis[i^p[i]] = 1;}if(vis[i^q[i]]){pri(q[i]*4+3);pri(q[i]*4+1);}else{pri(q[i]*4+1);pri(q[i]*4+3);vis[i^q[i]] = 1;}}printf("\n");
}
int main()
{int t;scanf("%d", &t);while(t--)slove();return 0;
}
)
