AtCoder Regular Contest 133 D Range XOR
洛谷传送门
AtCoder 传送门
很典但是并不会做……
设 \(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 一下即可。