不会做。
考虑拆分成前缀和的形式。设 \(w_i = 1 \oplus 2 \oplus \cdots \oplus i\)，打表容易发现：
\[w_i = \begin{cases} i & i \equiv 0 \pmod 4\\ 1 & i \equiv 1 \pmod 4\\ i + 1 & i \equiv 2 \pmod 4\\ 0 & i \equiv 3 \pmod 4 \end{cases} \]现在问题变成了从 \([l - 1, r]\) 中选两个数 \(i, j\)，使得 \(w_i \oplus w_j = v\)。
左边界限制很烦人，容易容斥为 \([0, r]\)。
考虑按照 \(w_i, w_j\) 的 \(4 \times 4\) 种情况分类讨论。\((0, 2)\)，\((1, 3)\) 情况类似，可以先全局异或一个数使得 \(w_i, w_j, v\) 在二进制下后两位均为 \(0\)。
- \((1, 3), (1, 3)\)：发现当且仅当 \(v=0\) 时存在，且 \(i, j\) 可以取任意值；
- \((1, 3), (0, 2)\)：发现只要存在 \(i\)，那么任意一个 \(j\) 都可以选；
- \((0, 2), (0, 2)\)：将所有的数都除以 \(4\)，问题抽象为：求 \(x \in [0, a], y \in [0, b], x \oplus y = v\) 的方案数。数位 DP 容易求出答案。
除掉 \(v = 0, i = j\) 的方案数再除以 \(2\) 就是原答案。（需要保证 \(i < j\)）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 70, P = 998244353;
long long l, r, v;
int off[4] = { 0, 1, 3, 0 };
int f[MAXN][2][2];
void add(int &a, int b) {
a += b;
if (a >= P) a -= P;
}
int solve2(long long a, long long b, long long v) {
memset(f, 0, sizeof f);
f[60][1][1] = 1;
for (int i = 60; i >= 1; i--) {
int n = a >> (i - 1) & 1;
int m = b >> (i - 1) & 1;
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) if (f[i][x][y]) {
for (int p = 0; p <= (x ? n : 1); p++) {
for (int q = 0; q <= (y ? m : 1); q++) {
if ((p ^ q) == (v >> (i - 1) & 1)) {
add(f[i - 1][x && (p == n)][y && (q == m)], f[i][x][y]);
}
}
}
}
}
}
int ans = 0;
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
add(ans, f[0][x][y]);
}
}
return ans;
}
int solve(long long a, long long b, long long v) {
if (a < 0) return 0;
int ans = 0;
for (int x = 0; x < 4; x++) {
for (int y = 0; y < 4; y++) {
long long c = (a + 4 - x) / 4, d = (b + 4 - y) / 4;
long long t = v ^ off[x] ^ off[y];
if (t % 4 != 0) continue;
if (x % 2 == 1) {
if (y % 2 == 1)
if (t == 0) ans = (ans + (c % P) * (d % P)) % P;
else
if (t / 4 + 1 <= d) ans = (ans + c) % P;
} else {
if (y % 2 == 1)
if (t / 4 + 1 <= c) ans = (ans + d) % P;
else
ans = (ans + solve2(c - 1, d - 1, t / 4)) % P;
}
}
}
return ans;
}
int main() {
scanf("%lld%lld%lld", &l, &r, &v);
l--;
int ans = (solve(r, r, v) - 2ll * solve(l - 1, r, v) + solve(l - 1, l - 1, v) + 2 * P) % P;
if (!v) ans = (ans - (r - l + 1) % P + P) % P;
ans = 1ll * ans * ((P + 1) / 2) % P;
printf("%d\n", ans);
return 0;
}