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,...\) のビット表示を確認すると、
| 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