ARC 补题目录

很巧妙的一道数位 DP。
求：

$$\displaystyle\sum_{l=L}^{R}\displaystyle\sum_{r=l}^{R}[(\oplus_{i=l}^{r}i)=V]$$

显而易见的先把这个式子改成前缀异或和形式，定义 $s_{i}=\oplus_{i=0}^{i} i$。

$$\displaystyle\sum_{l=L-1}^{R-1}\displaystyle\sum_{r=l}^{R}[(s_r \oplus s_l)=V]$$

然后我们把它整的好看一点，便于计算：

$$\displaystyle\sum_{l=L-1}^{R}\displaystyle\sum_{r=L-1}^{R}[(s_r \oplus s_l)=V]$$

在 $V=0$ 的时候会多计算 $r-l+2$ 个答案，同时对于所有情况，都会把 $[l,r]$ 和 $[r,l]$ 计算两遍。但这不重要，最后特判就可以了。
然后发现一个性质

i % 4 == 0: s[i] = i
i % 4 == 1: s[i] = 1
i % 4 == 2: s[i] = i + 1
i % 4 == 3: s[i] = 0

对于 $s_{i} = 0 // 1$ 常量的情况可以直接计算。
其他的就会发现，去掉后面两位再做数位 DP 即可，由于改成了前缀形式，直接计算：

$$\displaystyle\sum_{i=0}^{\lfloor \frac{n}{4} \rfloor}\displaystyle\sum_{j=0}^{\lfloor \frac{m}{4} \rfloor} [i \oplus j = \lfloor \frac{V}{4} \rfloor]$$

然后就是板子了。

#include <bits/stdc++.h>
using namespace std;
const int s[4] = {0, 1, 3, 0};
const int mod = 998244353;
long long l, r, v;

long long qmi(long long a, long long k) {
    long long res = 1ll;
    while (k) {
        if (k & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        k >>= 1;
    }
    return res;
}

long long cnt(long long n, int x) {
    if (x == 0 || x == 2) return 1ll;
    return ((n >> 2) + ((n & 3) >= x)) % mod;
}

long long f[75][2][2];
long long DP(int u, bool f1, bool f2, long long n, long long m, long long v) {
    if (u < 0) return 1ll;
    if (f[u][f1][f2] != -1) return f[u][f1][f2];    //记忆化
    int r1 = (f1 ? (n >> u) & 1 : 1), r2 = (f2 ? (m >> u) & 1 : 1);
    long long ans = 0;
    for (int i = 0; i <= r1; i++)
        for (int j = 0; j <= r2; j++) {
            if ((i ^ j) != ((v >> u) & 1)) continue;    //不满足条件
            (ans += DP(u - 1, f1 & (i == r1), f2 & (j == r2), n, m, v)) %= mod;
        }
    return f[u][f1][f2] = ans;
}

long long solve(long long n, long long m) {
    if (n < 0 || m < 0) return 0ll;
    long long ans = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            if ((s[i] ^ s[j]) != (v & 3)) continue;
            memset(f, -1, sizeof f);
            long long x, y;
            if (i & 1) x = 0; else x = (n >> 2) - (i > (n & 3));
            if (j & 1) y = 0; else y = (m >> 2) - (j > (m & 3));
            ans += DP(58, 1, 1, x, y, v >> 2) *
                    cnt(n, i) % mod * cnt(m, j) % mod;
            ans %= mod;
        }
    return ans;
}

int main() {
    scanf("%lld%lld%lld", &l, &r, &v);
    long long inv2 = qmi(2, mod - 2);
    long long Ans = solve(r, r) - solve(l - 2, r) * 2 + solve(l - 2, l - 2);
    Ans = (Ans % mod + mod) % mod;
    // cout << Ans << endl;
    if (v == 0) Ans = (Ans - ((r - l + 2) % mod) + mod) % mod;
    Ans = (Ans * inv2) % mod;
    printf("%lld\n", Ans);
    return 0;
}