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~B$ に出てくる $1$ の数が偶数個か奇数個か数えれば、$f(1,B)$ の各ビットがわかる。 $A=0$ の $1,2,3,…$ のビット表示を確認すると、
| 10進数 | 2進数 |
|---|---|
| 0 | 00000000 |
| 1 | 00000001 |
| 2 | 00000010 |
| 3 | 00000011 |
| 4 | 00000100 |
$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