题解归档 - cf2225D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225D
• 本地来源：problems/cf2225D/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/D
• 原始标题：cf2225D - Exceptional Segments

思路

cf2225D - Exceptional Segments

Pattern

Count zero-xor subsegments through a fixed point by prefix xor classes.

Claim

Let pref(t) = 1 xor 2 xor ... xor t, with pref(0)=0.
A segment [l,r] has xor 0 iff pref(l-1) = pref(r).

For every counted segment, a=l-1 lies in [0,x-1] and b=r lies in [x,n], so a < b.

The prefix xor pattern is:

• t % 4 == 0: pref(t)=t
• t % 4 == 1: pref(t)=1
• t % 4 == 2: pref(t)=t+1
• t % 4 == 3: pref(t)=0

For two different positions a<b, equal prefix values can only be 0 or 1.
All values produced by the t%4==0 and t%4==2 cases are unique at their own position.

Necessary / Sufficient

It is necessary and sufficient to count:

• left positions a in [0,x-1] with prefix value 0, times right positions b in [x,n] with prefix value 0;
• plus the same product for prefix value 1.

pref(t)=0 at t=0 and all t>=3, t%4==3.
pref(t)=1 at all t%4==1.

Complexity

Each test case is O(1).

Checks

• Sample passed.
• Random stress against direct brute force for n<=80: 1000 cases passed.

代码

来源：problems/cf2225D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll MOD=998244353;

ll cnt(ll L,ll R,ll rem){
    if(L>R) return 0;
    if(L<0) L=0;
    ll first=L;
    ll d=(rem-first%4+4)%4;
    first+=d;
    if(first>R) return 0;
    return (R-first)/4+1;
}

ll cnt0(ll L,ll R){
    if(L>R) return 0;
    ll res=0;
    if(L<=0&&0<=R) res++;
    res+=cnt(max(3LL,L),R,3);
    return res;
}

ll cnt1(ll L,ll R){
    return cnt(L,R,1);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n,x;
        scanf("%lld%lld",&n,&x);
        ll a0=cnt0(0,x-1)%MOD;
        ll b0=cnt0(x,n)%MOD;
        ll a1=cnt1(0,x-1)%MOD;
        ll b1=cnt1(x,n)%MOD;
        printf("%lld\n",(a0*b0+a1*b1)%MOD);
    }
    return 0;
}