ABC141 F. Xor Sum 3
問題
N個の非負整数A_iが与えられる。
これを1個以上が属する2つのグループにわける。
各グループ内の整数のすべてのxorを取ったものの和を最大化するような選び方をした場合、その最大値を返せ。
制約
- 2 <= N <= 10^5
- 0 <= A_i < 2^60
解法
すべての与えられた整数のxorを取ったものをsとする。
このとき、各ビットごとに見ると、
- 1になっている→2つのグループにどう分けても1の数が奇数個なので、関係ない
- 0になっている→グループの選び方によっては、0と0、または1と1にできる
となっていることがわかる。
なので、sのビットが0になっている部分で1と1を作れるほど桁上りが発生して値を大きくできる。また、そのようなビットは上の桁でできるほど値がおおきくなりうれしいので、上の桁から1と1が作れるようにグループを作りたい。
最終的な答えは、「(sの1になっている部分のxor)＋(sの0になっている部分でできるだけ上位の桁から1と1に分けた場合のグループのxor)*2」になる。
前者はすぐ作れるが、後者はどうやったら求められるか？が問題。
sの1になっている部分を0につぶしたA_iを、B_iとする。
ここで、B_iのビット列を縦に並べた行列を考える。
入力例1の(3,6,5)の場合、 0 1 1 1 1 0 1 0 1
この行列において、いくつかの行を選んでxorを取ったもの＝片方のグループになる。
B_iは全部のxorを取ると0になるため、選ばなかったもののグループのxorは選んだもののグループのxorと同じになる。
したがって「Bからいくつか選び、それらのxorの最大値」を求めたい、という問題になる。(0個または全部選ぶ場合はxorは0なので、無視して考えても問題ない)
これは、xorの掃き出し法を使うと求められる。
あるB_iに対して、B_j (i!=j)とのxorを取ると、B_iは(B_i xor B_j)になるが、それはB_iとB_jを選んだとき(「iとjを選ぶ行為」とxorを取った後で「iを選ぶ行為」が同じ)の値になり、(B_i xor B_j)とB_jを選んだ場合は、B_iだけを選んだとき(「iだけを選ぶ行為」とxorを取った後で「iとjを選ぶ行為」が同じ)の値になる。
このように行に対してxorを取る操作は、対応関係が取れるので、各ビットで1になっているものが1つだけになるように行のxorを取れば、「そのビットにおいて、1が立っているものを選んでおけば、他の0になっているものをどのように選んでもよい」とできる。
これを上位の桁から掃き出し法で行っていく。(1がどれも立っていないビットの場合は何もできないので無視)
最終的に、全部の行のxorを取れば最大値が得られる。
