ABC121D XOR World ~XORに関する法則~

atcoder.jp
O(1)

atcoder.jp
O(log B)

[A,B]の区間の自然数をすべてXORしたらいくつになるでしょう？

XORは同じものを重ねると0になり、0はXORの単位元なのでいくらあっても演算結果に影響がないので、累積和の要領で差分みたいなのをとればいい。

また、解説にもあるように、(2 * k)^(2 * k + 1) = 1 となる。(下一桁以外は必ず同じ)これを利用すればいい感じにとける。

そうでなくとも、2^k(k >= 1)の位は0が連続してる部分か1が連続してる部分か(0000111100001111...みたいな)を見て、1が連続の部分ならば連続してる数を数える。
1の位の時は、01010101...と連続して、1が連続することはないので、mod 4をとって1or2の時に1となりそれ以外に0になる。これを実装すればO(log B)の解法となりこれでもとける。

～～～まとめ～～～

・　XORの基本的な性質は下のサイト様から確認できる。
qiita.com

・　k:自然数　(2 * k)xor(2 * k + 1) = 1である