codeFlyer 2018 final D - 数列 XOR(600)

• 問題

解法

考察

• XOR swapによりswapが可能( a ^= b, b ^= a )
• これによってa_i, a_j (i!=j) で操作ができる
• あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能
• そのような要素は {1101, 1001} のような1bitだけ異なる数があっても作ることができる
• それが作れれば {a} と {b} でその要素ができるか?という基準で判定さえすればOK
• しかし上の {1101, 1001} の 1001のように2bitが必ず同じように現れることもありえる
• 全ての組み合わせは2⁶⁴で判定するのは無理だし..?

上の操作が行列の行基本変形に酷似していることに頑張って気付こう.
結果的にいえば, 1bit目が立っているものを調べてそのような要素(a_rank)がなければそのbitは無視し,あるならばその他の要素(a_i)をその要素とのxor (a_i ^= a_rank)にして消していくというのをやれば良い.
これはxorをmod2での加算と見て,bit方向を列と見たときのGaussの消去法に他ならない.
またxorは逆操作が可能なので {a} -> {b} という操作が可能か?という問題でなく, {a}, {b} を共に共通の標準形にできるか?という問題に言い換えることができる.
よって {a}, {b} に上の操作をして,等しくなればYes,そうでなければNoになる.

メモ

• 逆操作が可能なら共通要素に変換できるか?という問題になる
• bitを列にして行列で捉える味方

コード