まず、答えが絶対にNOとなる場合を導きます。
操作回数の総合計は回で、これは奇数です。とすると、Aから奇数回操作をかけると立っているbitの本数の偶奇が逆転することがわかります。結局、AとBで立っているbitの数の偶奇が一致していては構築できない、ということがわかりました。
ここからは、AとBで立っているbitの本数の偶奇が異なるとして、その場合必ず構築可能なように話を進めていきます。
まず、N=3,A=4,B=3とします。
二進法で表すと、A=100,B=011となります。
まず、AとBで異なるbitをひとつ見つけます。これは必ず存在することはわかります。(Aの立っているbitの本数とBの立っているbitの本数の偶奇は必ず異なるので)
すると、それを前半と後半で固定したくなります。(図の赤丸のイメージ)
ので、これを前半と後半で固定します。(図の橙)
図での1の連続と0の連続のつなぎ目の部分に何か同じものを入れると、その間の編集距離がちょうど1bitになります。
ここで、ここには何を入れるのが適切でしょうか。
まず、AとBの間で固定したbitは異なるものであるということに留意します。
すると、AとBの残りの部分では立っているbitの本数の偶奇が一致します。(図の緑)
ここで、Aの残りの部分のうち、まだ確定していないbitをひとつひっくりかえしたものXを考えます。すると、これはAの残りの部分ともBの残りの部分とも立っているbitの本数の偶奇が異なります。(図の青)
すると、(図では下2桁について)、XをいわばA',B'とした1つ小さいサイズの問題がふたつ生まれます。これを、問題のサイズが1になるまで繰り返すと、全ての問題間で「確定したbitの集合はすべての問題についてどこかが相異なり、問題のサイズをひとつ落とす」を繰り返しているので、これによってできる順列は必ず問題文の条件を満たします。
この流れを最後までやると、このような感じになります。
これを、bit演算を使って実行すると、この問題を解くことができます。
いくつか使うbit演算の例を示しておきます。
AとBの下からkbit目が異なるかどうか ((A>>(k-1))%2) != ((B>>(k-1))%2)
Aの下からkbit目を反転 A^=(1<<(k-1))
