题解：CF2225D Exceptional Segments
TobeeckW
·
·
题解
这道题一开始打算使用 01 字典树，但是发现数据量极其庞大，绝对会 TLE，后来才看到题里是连续的数……（QwQ）还是仔细读题。
首先我们要了解的知识点：
- 当我们想统计 0 \sim R 的范围内，有多少个数除以 d 余数为 m。核心公式是：cnt = \lfloor (R-m)/d \rfloor + 1（向下取整）。
- 异或前缀和：我们知道异或的性质，从而可以通过异或前缀和来计算出区间 l \sim r 的异或值。设前缀和数组为 prefix，也就是 prefix[l-1] \oplus prefix[r]。相当于我们要在 x 左右两边找 l 和 r，使得满足 prefix[l-1] = prefix[r]。
- 连续的数异或的性质：我们可以打表看一下：
1 = 1
1 \oplus 2 = 0
1 \oplus 2 \oplus 3 = 3
1 \oplus 2 \oplus 3 \oplus 4 = 0
1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 = 5
我们不难发现一个规律，对于前 i 个数的异或前缀和：
$i \bmod 4 = 1$ 时，$prefix[i] = 1$。
$i \bmod 4 = 2$ 时，$prefix[i] = i + 1$。
$i \bmod 4 = 3$ 时，$prefix[i] = 0$。
了解了以上内容，这个题基本就出来了。
我们通过异或前缀和，把题意简化为：在 $x$ 左右两边，找两个数的前缀异或值相等的方案数。
我们可以发现，如果两个数的前缀异或值相等，那么只能是这两个数的值相等。由于 $i$ 是递增的，所以当 $i \bmod 4$ 为 $0$ 或者 $2$ 的时候，这个数在整个数组中只出现了一次，是不可能和其他数的前缀异或值相等的。
所以，能匹配的情况只有两种：两端都是 $0$，或者两端都是 $1$。
那么，我们只需要统计 $0 \sim x-1$ 中 $0$ 和 $1$ 的个数，以及 $x \sim n$ 中 $0$ 和 $1$ 的个数，设为 $c0l, c0r, c1l, c1r$。
那么答案就变成了：$c0l \times c0r + c1l \times c1r$。
我们一定记得在过程中要取模！不然会溢出。
AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
int t;
int n, x;
void solve(){
cin >> n >> x;
int c0l = 1 + x / 4, c0r = 1 + (n + 1) / 4 - c0l;
int c1l = (x + 2) / 4, c1r = (n + 3) / 4 - c1l;
c0l %= MOD, c0r %= MOD, c1l %= MOD, c1r %= MOD;
int ans = (c0l * c0r) % MOD;
ans = (ans + (c1l * c1r) % MOD) % MOD;
cout << ans << '\n';
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}