Make Good - goodbye 2019 c - tac

#xor

数列に同じ 2 数を足しても xor は変わらない
sum は 2 * その数増える

2 * xor = sum にしたい
数列に足す 2 数は, (2 * xor - sum) / 2
ただし, 2 * xor - sum が偶数かつ 2 * xor ≥ sum
2 * xor は偶数より, sum が偶数

残り 1 数足せる
それで sum が偶数かつ 2 * xor ≥ sum の条件を満たすようにする

sum を偶数にするから, sum が奇数なら 1 を足す

sum はどれくらいになるか
$10^5 * 10^9 < 2^{47} < 2^{50}$

$2^{50}$ + (sum % 2) を sum に足すと sum < $2 * 2^{50}$
また, $2^{50}$ + (sum % 2) を数列に足すと xor ≥ $2^{50}$ (そんな大きな bit が立ってないので)
2 * xor ≥ $2 * 2^{50}$ > sum

単純なケースを考える
2 数を足す場合を考える
S + a + b = 2 * (X ^ a ^ b)

仮に右辺の X を打ち消そうとしても左辺に X が出てくる

右辺に 2 * X があるので左辺にも出る
左辺に S があるので右辺にも出る

右辺が 2 * という形なので, 左辺に S がもう 1 つあるとする
a + b = S + 2X

X ^ a ^ b = S + X
a = X, b = S + X