题解：CF2225D Exceptional Segments

· · 题解

首先可以打表找到规律，然后尝试证明。

注意到 0 \oplus 1 \oplus 2 \oplus 3 = 0，又因为 4,5,6,7 相当于 0,1,2,3 每个数加了 4 对最低两位不造成影响，高位上直接全部异或掉，同理有 4 \oplus 5 \oplus 6 \oplus 7 = 0，所以 0 \oplus 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus 7 = 0，进而推广到 \oplus_{i=0}^{4n+3} i = 0，其中 n \in \mathbb{N}。所以可以构造出一个数列 0,3,7,11,\dots，在里面任选两个数 l, r，有 \oplus_{i=l+1}^r i = 0。

同理可构造出数列 1,5,9,13,\dots。

对于两个数列分别考虑，统计每个数列值属于 [0,x) 和 [x,n] 的数的个数，乘法原理即可。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int T, n, m;
void GOGOGO() {
    cin >> n >> m;
    int ans = 0, res1 = (m + 3) / 4 % mod;
    int k = m;
    while ((k + 3) % 4) k++;
    if (k == m) res1 = (res1 - 1 + mod) % mod;
    if (n >= k) ans = (ans + res1 * ((n - k) / 4 % mod + 1) % mod) % mod;
    res1 = ((m + 1) / 4 + 1) % mod;
    k = m;
    while ((k + 1) % 4) k++;
    if (k == m) res1 = (res1 - 1 + mod) % mod;
    if (n >= k) ans = (ans + res1 * ((n - k) / 4 % mod + 1) % mod) % mod;
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) GOGOGO();
    return 0;
}
/*
1 5 9 13 ... 4n+1

0 3 7 11 15 ... 4n+3
*/

:::