很典但是并不会做……
设 \(s_i = \oplus_{i=0}^n i\)，所求即为：
\[\sum\limits_{l=L-1}^R \sum\limits_{r=l+1}^R [s_l \oplus s_r = V]
\]
考虑把它化成下界相同的形式，即求：
\[\sum\limits_{l=L-1}^R \sum\limits_{r=L-1}^R [s_l \oplus s_r = V]
\]
记 \(f(n, m) = \sum\limits_{i=0}^n \sum\limits_{j=0}^m [s_i \oplus s_j = V]\)，上式即为：
\[f(R, R) - 2f(L - 2, R) + f(L - 2, L - 2)
\]
接下来考虑求 \(f(n, m)\)。
发现 \(s_i\) 很有规律，具体地：
- \(i \bmod 4 = 0, s_i = i\)；
- \(i \bmod 4 = 1, s_i = 1\)；
- \(i \bmod 4 = 2, s_i = i + 1\)；
- \(i \bmod 4 = 3, s_i = 0\)。
考虑枚举 \(l,r\) 二进制下的后两位（前面位与后面位无关），那么现在大概是要求：
\[\sum\limits_{i=0}^{\left\lfloor\frac{n}{4}\right\rfloor} \sum\limits_{j=0}^{\left\lfloor\frac{m}{4}\right\rfloor} [i \oplus j = \left\lfloor\frac{V}{4}\right\rfloor]
\]
这个随便数位 dp 一下即可。
- AtCoder Regular Contest Range 133atcoder regular contest range atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest