AtCoder ABC 121 D - XOR World

https://atcoder.jp/contests/abc121/tasks/abc121_d

ビットごとの排他的論理和は二回繰り返すと元に戻り、可換で結合法則を満たすことから、

$f(A,B)=A \veebar A+1 \veebar \cdots \veebar B$

$= (0 \veebar 2 \veebar \cdots \veebar A-1) \veebar (0 \veebar 2 \veebar \cdots \veebar B)$

$= f(1,A-1) \veebar f(1,B)$

だから、$A=0$ の場合に帰着される。

それぞれの桁毎に、$0 \sim B$ に出てくる $1$ の数が偶数個か奇数個か数えれば、$f(1,B)$ の各ビットがわかる。 $A=0$ の $1,2,3,...$ のビット表示を確認すると、

$1$ の位は $0 \rightarrow 1 \rightarrow 0 \rightarrow 1 \rightarrow \cdots$ と1つごとに切り替わり、 $2$ の位は $0 \rightarrow 0 \rightarrow 1 \rightarrow 1 \rightarrow \cdots$ と2つ毎に切り替わり、と規則的になっている。

$2^i$ 桁目のビットを考えよう。$i=0$ の時は $B \equiv 1 \mod 4$ なら $1$, それ以外なら $0$ が立っている。

$i \ge 1$ であれば、$2^{i+1}$ 毎に $1$ が $2^i$ 個(偶数個)出てくるから、$1$ の出現数の偶奇は $(B+1) \mod 2^{i+1}$ で考えれば良い。 $2^{i+1}$ 個ごとの $0/1$ の出現順は、最初に $0$ が $2^i$ 個続き、そのあと $1$ が $2^i$ 個続くから、 $1$ の数は、$\max(0, ((B+1) \mod 2^{i+1}) - 2^i)$。 この数が偶数なら $0$, 奇数なら $1$ のビットが立っている。

(実装は結構手間取りました) https://atcoder.jp/contests/abc121/submissions/32474342