D - Range XOR - AtCoder Regular Contest 133
解説を理解するのに時間かかった...
以下はkmjpさんのブログ記事
AtCoder ARC #133 : D - Range XOR - kmjp's blog
を読んで理解したものなのですが、備忘録として残します。
問題
整数L, R, Vが与えられる。
L<=l<=r<=Rで、lからrまでのxorがVになるようなl, rの組は何通りあるか。
解法
f(x) := 0~x-1までのxorを取ったものとすると、mod4で周期があり
f(4n+0) = 0
f(4n+1) = 4n
f(4n+2) = 1
f(4n+3) = 4n+3
のようになります。
以後桁dpで解く
l, rを4で割った余りについて条件を満たすものを数え上げると
X(l, r) := [l, r)のxorとすると
X(l, r) = f(l) ^ f(r)ですが
l, rの値からX(l, r)を4で割った余りはO(1)で分かります。
少なくとも4で割った余りが正しいかについてはそれで判定が出来て
bitで2桁よる上の物について、L < Rになるようにbit毎に値を決めていく
この際、4nが付いている者はここで選んだbitが値に反映され
4nが付いていない物はここで選んだbitが値に反映されない。
この上でxorがVになるように決めてやればいい。
最終的にL, Rの大小関係は4で割った余りを反映して考える事に注意
