https://atcoder.jp/contests/ttpc2019/submissions/13679593
- xor 演算は移項できる A xor B = X ⇔ B = X xor A
- 「xor 演算は(ビットサイズが同じなら)X以上のB → X以下の値2個 に分解できる」と暗記する
- つまり B = X xor B' (X < B, B' < X) が構築できる
各桁の01ビットを数えても良いが、XOR演算でシンプルに解ける。A xor B = X ⇔ B = X xor A なので、-1以外の全てとXを排他的論理和した答えをBとし、-1のうち1個をBに置換して残りを0にすれば構築できる。計算量はになる。
ただし、-1でないがXを超えるテストケースもあるので、BがXのビットサイズを超えていたら構築不可能とする。また、BとXのビットサイズが同じ場合、X<Bでも構築可能になるので注意する。具体的には、B xor X = B'としてBをXとB'に分解する工夫をして、2個の-1をXとB'に置換する方法で構築する。