题解：CF2225D Exceptional Segments

· · 题解

前言：滚木滚木 + 恶心取模。

Solution

我们先定义一个前缀异或数组 p[i]=1\oplus2\oplus\cdots \oplus i，这样区间 [l,r] 异或和为 0 也就是 p[l-1]=p[r]，所以题目也就转化成了求 1≤l≤x≤r≤n 中 p[l-1]=p[r] 的方案数。

然后考虑 p 数组的特殊性质，手推一下可以得出：

i \bmod 4 p[i]
0 i
1 1
2 i+1
3 0

枚举可得满足条件的只有三种情况：

然后分别计算上述三种贡献然后相加就可以了，注意取模不要炸了。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M=998244353;
int T,n,x;
int czf(int l,int r,int f){
    int fir=l+((f-l)%4+4)%4;
    if(fir>r)return 0;
    return ((r-fir)/4+1)%M;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>x;
        int ans=0;
        ans=(ans+czf(0,x-1,1)*czf(x,n,1))%M;
        ans=(ans+czf(0,x-1,3)*czf(x,n,3))%M;
        ans=(ans+czf(x,n,3))%M;
        cout<<ans<<'\n';
    }
}