\(0 \leq k\) について，\(w_k=0 \oplus 1 \oplus \cdots \oplus (k-1)\) と定義します．

求めたいのは，\(L \leq i < j \leq R+1\) であって，\(w_i \oplus w_j=V\) となる \((i,j)\) の個数です．

まずこれを少し変形すると，\(0 \leq i < A, 0 \leq j < B, w_i \oplus w_j=V\) を満たす \((i,j)\) の個数を数える，というサブルーチンに帰着できます．

\(w_k\) の値は，\(\bmod 4\) で分類すると簡単に書けます． 具体的には

• \(w_{4x}=0\)
• \(w_{4x+1}=4x\)
• \(w_{4x+2}=1\)
• \(w_{4x+3}=4x+3\)

となります． よって，\(i,j\) の \(\bmod 4\) を固定し，\(16\) 通りすべてについて問題を解けばよいです． 実際には \((4x,4x+2)\) および \((4x+1,4x+3)\) のケースはまとめることができるため，場合分けは \(4\) 通り程度で済みます．

この中で最も非自明なのは \(i,j\) がどちらも \((4x+1,4x+3)\) であるケースです． この場合は，さらに次のような小問題を解く必要があります．

• 整数 \(C,D,W\) が与えられるので，\(0 \leq c < C, 0 \leq d < D, c \oplus d = W\) を満たすペア \((c,d)\) の個数を求めよ．

これは bit DP やメモ化再帰で高速に解くことが可能です．

上記を実装することで，\(O(poly(\log \max(R,V)))\) 時間で問題を解くことができます．

解答例(c++)