题解：CF2225D Exceptional Segments

zhangjizhi · 2026-04-24 20:19:09 · 题解

题意

给你一个 [1,2,\dots,n] 的序列，求满足以下要求的区间数：

• 1 \le l \le x \le r \le n
• l \oplus (l+1) \oplus \dots \oplus r = 0

分析

遇到连续一段数的异或和，我们有一个经典结论（设 Sum_i=1 \oplus 2 \oplus \dots \oplus i）：

• 当 n \bmod 4=0 时，Sum_i=n
• 当 n \bmod 4=1 时，Sum_i=1
• 当 n \bmod 4=2 时，Sum_i=n+1
• 当 n \bmod 4=3 时，Sum_i=0

证明

由异或的定义，可得 2k \oplus (2k+1)=1（前面几位都相同，异或出来为 0；最后一位不同，异或出来是 1），所以可以得出 4k \oplus (4k+1) \oplus (4k+2) \oplus (4k+3)=0，又由于 x \oplus 0=x，所以可以把一开始的 0 忽略，于是我们证明出了第四个结论，前三个结论也可以有第四个结论推出。

回归本题

若 l \oplus (l+1) \oplus \dots \oplus r = 0，则 Sum_r \oplus Sum_{l-1}=0，也就是 Sum_r=Sum_{l-1}。我们可以发现，只有当 r \bmod 2=1 且 (l-1) \bmod 2=1 且 r \bmod 4=(l-1) \bmod 4 时才能使 Sum_r=Sum_{l-1}。（理解：对于不同的 x，若 x \bmod 2=0 时，Sum_x 互不相等，所以必须使 x \bmod 2=1）

对此，我的实现就是去写一个 find 函数，找到一段区间内的除以 4 余 k 的数量，则答案为 (fnd(x,n,1)*fnd(1,x,2)+fnd(x,n,3)*fnd(0,x,0)。（由于可以使开头为 0 并忽略，所以说要加上一开始的 0）

AC code

代码中部分实现与文中不同。注意：这题要在所有地方取模，否则会炸。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,MOD=998244353;
int t,n,m;
string s,t1;
int a[N],b[N],dp[N];
int fdd(int r,int x)
{
    int ans=r/4;
    if(r%4>=x) ans++;
    return ans%MOD;
}
int fnd(int l,int r,int x)
{
    return ((fdd(r,x)-fdd(l-1,x))%MOD+MOD)%MOD;//前缀和
}
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cout<<((fnd(m,n,1)*fnd(1,m,2)%MOD+fnd(m,n,3)*(fnd(1,m,0)+1)%MOD)%MOD+MOD)%MOD<<'\n';//与文中一致，有些地方不太一样

    }
    return 0;
}