题解：CF2225D Exceptional Segments

fengzhaoyu · 2026-04-24 20:08:25 · 题解

思路

首先区间异或可以转化成前缀异或和。

只有前 l-1 异或和等于前 r 异或和相等，区间 [l,r] 才是合法区间。

注意到前缀异或和为 1，0 的每四个出现一次，其余的前缀结果都只会出现一次。原因也很好证：2n\bigoplus 2n+1=1，将其两两成对，因此前奇数对异或和为 1，偶数对为 0。

从 1 开始把前缀异或和每四个分成一组，第 1 个为 1，第 3 个为 0。

所以有贡献的只能是前缀和为 1，0 的。

你就计算 x 两边 0，1 个数即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}
const int N=2e5+15,mod=998244353;
void work()
{
    int n=read(),x=read();
    int l=(x-1)/4+((x-1)%4>=1);
    l%=mod;//及时取模
    int r=n/4+(n%4>=1);
    r%=mod;
    int cnt1=l*(r-l+mod)%mod;//1
    l=(x-1)/4+((x-1)%4>=3);
    r=n/4+(n%4>=3);
    l%=mod;
    r%=mod;
    int cnt2=(l+1)*(r-l+mod)%mod;//0，注意前缀0也有一个
    cout<<(cnt1+cnt2)%mod<<"\n";
}
signed main()
{
    int t=read();
    while(t--) work();
    // int ans=0;
    // for(int i=1;i<=100;i++)
    // {
    //  ans^=i;
    //  cout<<i<<" "<<ans<<"\n";
    // }
    return 0;
}