转化

Let \(s(n) = 0 \xor 1 \xor 2 \xor \dots \xor n\), then \(l \xor \dots \xor r = V\) is equivalent to \(s(r) \xor s(l - 1) = V\). Following the fact \(2n \xor (2n + 1) = 1\), it is not hard to see that \[ \begin{aligned} s(4k) &= 4k \\ s(4k + 1) &= 1 \\ s(4k + 2) &= 4k + 3 \\ s(4k + 3) &= 0 \end{aligned} \]

The problem can be rephrased as

Find the number of pairs of integers \((l, r)\) such that \(L - 1 \le l < r \le R\) and \(s(l) \xor s(r) = V\).

We now relax the \(l < r\) constraints and consider the following problem

Find the number of pairs of integers \((l, r)\) such that \(A \le l, r \le B\) and \(s(l) \xor s(r) = V\).

and let \(f(A, B)\) denote its answer.

Now remove the lower bound \(A\) and consider the following problem

Find the number of pairs of integers \((l, r)\) such that \(0 \le l \le M\) and \(0 \le r \le N\) and \(s(l) \xor s(r) = V\).

and let \(g(M, N)\) denote its answer.

One can verify that \(f(A, B) = g(B, B) - g(A - 1, B) - g(B, A - 1) + g(A - 1, A - 1)\). Now let’s focus on \(g(M, N)\). How can we compute \(g(M, N)\) efficiently? We divide all pairs \((m, n)\) such that \(0 \le m \le M\) and \(0 \le n \le N\) by \((m \bmod 4, n \bmod 4)\) into \(16\) classes. Now the problem becomes

Find the number of pairs \((l, r)\) that satisfy the following conditions

• \(0 \le l \le M\)
• \(0 \le r \le N\)
• \(l \equiv k_1 \pmod{4}\)
• \(r \equiv k_2 \pmod{4}\)
• \(s(l) \xor s(r) = V\)

This problem can be solved by bit DP in \(O(\log(\max(M, N, V)))\) time.

Code

#include <utils.hpp>
#include <m3.hpp>

void solve() {
  // s(4k) = 4k
  // s(4k + 1) = 1
  // s(4k + 2) = 4k + 3
  // s(4k + 3) = 0

  auto bit = [](int i, int b, int rem) -> int {
    if (rem == 0)
      return b;
    if (rem == 1)
      return i == 0;
    if (rem == 2)
      return i == 0 ? 1 : b;
    return 0;
  };

  LL(L, R, V);
  --L;

  auto count = [&](ll A, ll B) {
    if (A < 0 or B < 0)
      return 0_m;

    mint ans = 0;
    rng (rem1, 4)
      rng (rem2, 4) {
        vv<mint> dp(2, 2);// 0: equal, 1: less
        dp[0][0] = 1;
        down (i, 59, 0) {
          vv<mint> new_dp(2, 2);
          ll bit_A = A >> i & 1;
          ll bit_B = B >> i & 1;
          ll bit_V = V >> i & 1;
          up (x1, 0, 1)
            up (x2, 0, 1)
              up (b1, 0, 1)
                up (b2, 0, 1) {
                  if (i == 1 and (b1 != rem1 / 2 or b2 != rem2 / 2))
                    continue;
                  if (i == 0 and (b1 != rem1 % 2 or b2 != rem2 % 2))
                    continue;
                  if (x1 == 0 and b1 > bit_A or x2 == 0 and b2 > bit_B)
                    continue;
                  if ((bit(i, b1, rem1) xor bit(i, b2, rem2)) != bit_V)
                    continue;
                  int new_x1 = x1 or b1 < bit_A;
                  int new_x2 = x2 or b2 < bit_B;
                  new_dp[new_x1][new_x2] += dp[x1][x2];
                }
          swap(dp, new_dp);
        }
        up (x1, 0, 1)
          up (x2, 0, 1)
            ans += dp[x1][x2];
      }
    return ans;
  };

  mint ans = count(R, R) - 2 * count(L - 1, R) + count(L - 1, L - 1);
  if (V == 0)
    ans -= R - L + 1;
  pl(ans / 2);
}

References

https://atcoder.jp/contests/arc133/submissions/28688903