CF2225D Exceptional Segments

shiziyu111 · 2026-04-24 16:22:06 · 题解

首先我们观察有哪些段异或起来能等于 0。

不难发现假如我们可以将它们两两组队，这样的话异或的结果为 1。

证明也很简单，这些相邻的两个数除了最后一位相差了 1，其它位置都完全一样，它们长这样子：

?????????0
?????????1

前面的位置异或结果为 0，最后的结果为 1。

但是我们发现 1 只能单独组队，于是乎我们在前面补一个 0，即为将 n 和 x 都加 1，再求出总组数和 x 在的组数即可。

最后，我们就分成了许多组，而我们现在的目标就很简单：找到 l 和 r，使得他们经过某个组且满足 r-l+1 为偶数（因为偶数个 1 异或起来为 0）。

这一点靠分讨就能解决。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
void solve()
{
    int n,x;
    scanf("%lld%lld",&n,&x);
    n++;
    x+=2;
    n/=2;
    x/=2;
    if(x>n)
    {
        printf("0\n");
        return;
    }//注意，有可能 x 所在组比总组数还大。
    int ans=0;
    if(x%2==0)//大分讨，可能要手玩一下，当然如果你有更好的处理方法当我没说
    {
        ans+=((x/2)%mod)*(((n-x+1)/2)%mod)%mod;;
        ans+=((x/2)%mod)*(((n-x)/2+1)%mod)%mod;//如果你 Wa on test 6,有可能是取模有问题，别问我怎么知道的。
    }
    else
    {
        ans+=(((x+1)/2)%mod)*((n/2-x/2)%mod)%mod;;
        ans+=((x/2)%mod)*(((n-x)/2+1)%mod)%mod;
    }
    ans%=mod;
    printf("%lld\n",ans);
}
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}