ABC126 F. XOR Matching
問題
以下の条件を満たす長さ2^{M+1}の数列aが存在するなら1つ構築せよ。
- 数列aには、0以上2^M未満の整数がちょうど2つずつ含まれる
- a_i == a_jになるi,jについて、a_i xor ... xor a_j == Kとなっている
制約
- 0 <= M <= 17
- 0 <= K <= 10^9
解法
明確にわかる条件から抑えていく。
M=0のときは、K=0しかだめで、そのときの答えは「0 0」。
M=1のときは、同じくK=0しかだめで、答えは「0 0 1 1」か「1 1 0 0」。「0 1 0 1」のようなものは、0で挟まれる部分が1で、1で挟まれる部分が0になってしまう。
M=2の場合を考える。
まず、Kは2^M以上の場合、XORを取ってKが作れないので、構築できない。したがって、「K < 2^M」である必要がある。
M=2のときに現れる数字は、0 0 1 1 2 2 3 3の8つ。
実験として、これをnext_permutationで全通り試して、条件を満たすものを出力して観察すると、「Kを作って、それを両側から挟んでいるような形」が多く見受けられる。
具体的には、「X Y 0 K Y X」や「X Y K Y X」のような形ができている。
ここから、あるKについて、その両側を挟んでいくような形で考えると、同じ数字はxorを取ると0になるので、満たすことがわかる。
なので、Kを置いてその両側を挟むように他の数字を対象に置いていけばK以外の数字は条件を満たす。
ただ、Kが1つ余っており、これをどこかに置く必要があるが、すでに置いたKの両側には、0から2^M-1までの数字でKを除いた数字が並んでおり、このxorを考えるとKになっている。
(「0から2^M-1までの数字でKを除いた数字のxor」とKのxorが0にならないといけないため、Kであることがわかる)
したがって、「Kの両側に対称となるようにK以外の数字をならべ、最初か最後にKを置いたもの」は条件を満たすため、これを返せばよい。