【Codeforces 1168E】Xor Permutations
构造。
题目大意：
给定一个长度为 $2^n$ 的数列 $a_0,a_1,a_2,\ldots,a_{2^n-1}$。
要求找到两个长度为 $2^n$ 的 $0\sim 2^n-1$ 的排列 $p,q$，满足 $p_i$ 和 $q_i$ 的按位异或的结果为 $a_i$。
问是否有可能的方案，如果有则输出任意一种。
题解：
神仙构造题。
先判断无解。如果 $a$ 的异或和不为 $0$ 则无解。
我们考虑 $v_i$ 表示目前 $p_i$ 和 $q_i$ 的按位异或的结果。初始令 $p_i=q_i=i$，$v_i=0$。
我们依次检查每个位置，如果 $v_i\neq a_i$，则进行以下的操作：
- 令 $d=v_i\mathrm{\ xor\ }a_i$，令 $v_i$ 和 $v_{i+1}$ 都异或上 $d$。此时 $v_{i}$ 已经不等于 $p_i\mathrm{\ xor\ }q_i$ 了，$i+1$ 也类似。
- 执行
fix(i,i+1)。
其中 fix(i,j) 就是通过交换的操作，将 $p_i\mathrm{\ xor\ }q_i$ 修正为 $v_i$，$j$ 也一样的修正。
修正过程中，fix(i,j) 始终保证 $p_i\mathrm{\ xor\ }q_i\mathrm{\ xor\ }v_i=p_j\mathrm{\ xor\ }q_j\mathrm{\ xor\ }v_j$，而其他的 $a$ 和 $v$ 相等。
这个 fix(i,j) 的操作步骤如下：
- 令 $d=q_i\mathrm{\ xor\ v_i}$，找到位置 $k$ 满足 $p_k=d$。
- 若 $k=i$，则已经满足条件，修正完毕。
- 若 $k=j$，则交换 $p_i$ 和 $p_j$，修正完毕。
- 否则交换 $p_k$ 和 $p_i$，交换 $q_k$ 和 $q_j$，然后执行
fix(k,j)。
上面找 $p_k=d$ 的位置的时候，可以使用一个数组来记录 $p_i$ 对应的 $i$。
观察一下它还有哪些性质。我们发现 $j$ 是固定不变的，而 $p_i$ 也是不变的，因为每次都是将 $p_i$ 和 $p_k$ 交换后调用 fix(k,j)。这有助于我们分析复杂度。
我们需要证明，一个 $p_k$ 不会被选中两次。
我们假设一次操作前的状态是 $(p_k,q_k,v_k)$，$(p_i,q_x,v_y)(1)$，$(p_j,q_y,v_j)(2)$。
对其操作后变为：$(p_k,q_x,v_y)$，$(p_i,q_y,v_k)$，$(p_j,q_k,v_j)$。
然后又进行了若干递归以后，变成：$(p_k,q_x,v_y)$，$(p_i,q_m,v_n)$，$(p_j,q_n,v_j)$。
对其操作后变为：$(p_k,q_m,v_n)$，$(p_i,q_n,v_y)(3)$，$(p_j,q_x,v_j)(4)$。
那么：
由 $(1)$ 和 $(2)$ 可得：$q_y=p_i\mathrm{\ xor\ }q_x\mathrm{\ xor\ }v_y\mathrm{\ xor\ }p_j\mathrm{\ xor\ }v_j$。
由 $(3)$ 和 $(4)$ 可得：$q_n=p_i\mathrm{\ xor\ }q_x\mathrm{\ xor\ }v_y\mathrm{\ xor\ }p_j\mathrm{\ xor\ }v_j$。
所以 $q_y=q_n$。而 $y\neq n$，$q$ 又是一个排列，因此矛盾。
所以一个 $p_k$ 不会被选中两次。
那么在一次 fix(i,i+1) 中，只会进行 $O(2^n)$ 层的递归。而我们需要对 $2^n-1$ 个数 fix 一遍，因此时间复杂度 $O(4^n)$。
Code：
#include<cstdio>
#include<algorithm>
using std::swap;
const int N=4100;
int n,A[N],B[N],a[N],V[N],d,bel[N];
void fix(int x,int y){
int p=B[x]^V[x],t=bel[p];
if(t==x)return;
if(t==y){
swap(A[x],A[y]),swap(bel[A[x]],bel[A[y]]);return;
}
swap(bel[p],bel[A[x]]);
swap(A[t],A[x]),swap(B[t],B[y]),fix(t,y);
}
int main(){
scanf("%d",&n),n=1<<n;
for(int i=0;i<n;++i)scanf("%d",a+i),d^=a[i],A[i]=B[i]=bel[i]=i;
if(d)return puts("Fou"),0;
puts("Shi");
for(int i=0;i+1<n;++i)
if(V[i]!=a[i]){
int x=V[i]^a[i];
V[i]^=x,V[i+1]^=x;
fix(i,i+1);
}
for(int i=0;i<n;++i)printf("%d ",A[i]);
for(int i=0;i<n;++i)printf("%d ",B[i]);
return 0;
}