ABC121 D - XOR World

解いて解説を見たら自分の解法の百億倍スマートだったのですが、調べた感じ私と同じ解法が見つからなかったので何かに役立つことがあれば…

問題

atcoder.jp

解法

排他的論理和の性質から
$$f(A, B) = f(0, A - 1) \oplus f(0, B)$$
となります。
なので $f(0, N)$ を求めればよいことが分かります。そこで、簡単のため $g(N) := f(0, N)$ と書くことにします。

ここで、具体的に $N$ に値を入れて $0$ から考えると、$N = 2^n (n \geq 2)$ のときに $g(N) = N$ であることに気が付きます。
$g(N - 1) = 0$ であることを利用すると簡単に証明ができますが、証明は省略します。
※ ここで $N = 4n$ のときに $g(N) = N$ であることに気が付くと解説での解法にたどり着きます。

上記の性質を利用すると、
$N' = 2^n$ かつ $N' \leq N$ を満たすような最大の $N'$ での値は $g(N') = N'$ になるので、 $g(N' - 1) = 0$ となり
$$g(N) = N' \oplus (N' + 1) \oplus \dots \oplus N$$
が導かれます。
上式の項数の偶奇で $N$ の立っているビットの中で最上位のビットが $g(N)$ で立つかどうかが分かるので、最上位ビット以外の残りの計算は
\[
\begin{eqnarray}
&& (N' - N') \oplus (N' - N' + 1) \oplus \dots \oplus (N - N') \\
&=& 0 \oplus 1 \oplus \dots \oplus (N - N') \\
&=& g(N - N')
\end{eqnarray}
\]
となります。
したがって、再帰的に $g(N)$ を解くことができます。

注意点として、利用した性質が成り立つのは $N = 2^n (n \geq 2)$ のときのみなので $N \leq 3$ のときは場合分けする必要があります。

コード

下記のコードでは $N'$ をmsbという関数で求めています。
また、項数の偶奇を見るところでは $N'$ が偶数であることから $N$ の偶奇を見るだけでよいことを利用しています。
他にも、 $N - N'$ の部分が $N \oplus N'$ になっています。
atcoder.jp