ABC121 D - XOR World - ツバサの備忘録

解法

$[a,b]$ についてxorを取るとき、 $[0,b]$ についてxorを取った結果と、 $[0,a-1]$ についてxorを取った結果の2つの数字について、改めてxorを取ればよいです。ということで、 $[0,X]$ の区間の数字についてxorを取った結果を求めていく方法を探ります。
これは、それぞれの桁について、xorを取った最終的な結果が1か0かを計算し、最後に加算していけばよいです。
$2^{i}$ の桁についてみた時(ただし、 $i \neq 0$ とします)、0から順番にビットを見ていくと、これは $2^{i+1}-1$ までで1回ループをします。
$[0,2^{i} )$ ではビットが0、 $[2^{i},2^{i+1} )$ ではビットが1になっています。
そして、この1回のループでは、ビットが立っている数の個数が $2^{i}$ 個なため、xorをとると0になります。
ということで、まずは $X$ を $2^{i}$ で割った余りを $D$ としたとき、 $[0,D]$ についてのみ考えればよいことがわかります。
あとは、上記の区間についてビットが立っている個数を調べればよく、
$2^{i}$ 以上しかビットが立っていないことから、
$D$ から $2^{i}-1$ を引いた結果が奇数ならばこの桁の最終的な結果は1、偶数なら0、となります。
そして、 $i=0$ の場合ですが、これは4つ数字が増えるごとに1回ループをします。
ということで、4で割った余りが1か2であれば答えは1、そうでなければ0となります。
これを、 $X = a-1, b$ について操作を行い、それぞれの結果について改めてxorを取れば、答えとなります。

感想

今回は後ろから読んだため、最初に解いた問題となりました。
やりたいことはすぐに浮かんでいたのですが、ボケっとしていたら、引き算をする値や割り算をする値を間違えたり、コーナーケースである $i=0$ の部分にひっかかったりしました。
ただ、WAを出さずにそこそこの速度で通せたので、満足です。
~~後ろから解いていたので、提出コードのリンクを間違えてA問題のものにしてしまったのは秘密です~~