Codeforces #562 Div1 E. Xor Permutations

なんかすごくパズルっぽいな。
https://codeforces.com/contest/1168/problem/E

問題

(2^K)要素からなる数列Aが与えられる。
0～((2^K)-1)のPermutationの対P,Qのうち、A[i] = P[i] xor Q[i]となるものを構築できるか。
できるならその例を示せ。

解法

以下Editorialにある解法。

Aの全要素のxorを取ると、PとQの全要素のxorを取った値になるので0でなければならない。
よって、0でない場合は解なし。
それ以外の場合は必ず解があることを、構築法を持って示す。

まず適用にPとQを設定し、あとでAに合うよう調整していこう。
ある２要素A[i]、A[j]に対し、任意の(2^k)未満の整数xに対しA[i]=A[i] xor x、A[j]=A[j] xor xと置き換えられることを示す。
今j=i+1であるとし、さらにA[i] xor Q[i] = P[t]であるtがあるとする。
(tはiと一致するときは問題ないので、iとは不一致であるとする。)
今以下のようになっている。

• P[t] xor Q[t] != A[t]
• P[i] xor Q[j] != A[i]
• P[j] xor Q[j] と A[j]の関係は不明。

ここでP,Qを一部入れ替える。入れ替えた後の数列をP',Q'とすると、

• P'[t] = P[i], P'[i] = P[t]
• Q'[t] = P[j], Q'[j] = Q[t]

と入れ替えるこうすると、P'[i] xor Q[i]=P[t] xor Q[i] = A[i]ということで、i番目の要素は条件を満たした状態となる。
ただこの場合、tを次のiとして繰り返し調整していこう。
無限にこの手続きが続くことはなく、１回あたりO(数列長)程度までの繰り返しで終わる。

int N;
int A[1<<12];
int P[1<<12],RP[1<<12];
int Q[1<<12];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N=1<<N;
	x=0;
	FOR(i,N) {
		cin>>A[i];
		x^=A[i];
		P[i]=Q[i]=RP[i]=i;
	}
	if(x) return _P("Fou\n");
	FOR(i,N) {
		x=i;
		while((P[x]^Q[x])!=A[x]) {
			y=RP[A[x]^Q[x]];
			RP[P[x]]=y;
			RP[P[y]]=x;
			swap(P[y],P[x]);
			if(y>i) {
				break;
			}
			swap(Q[y],Q[i+1]);
			x=y;
		}
	}
	cout<<"Shi"<<endl;
	FOR(i,N) cout<<P[i]<<" ";
	cout<<endl;
	FOR(i,N) cout<<Q[i]<<" ";
	cout<<endl;
	
}

まとめ

こういうの思いつく気しないな。