CF2225D Exceptional Segments 题解

思路

定义 $f(i)=1\oplus 2\oplus\dots\oplus i$，有经典结论：
$$
f(i)=
\begin{cases}
i &\text{if } i\bmod 4=0\
1 &\text{if } i\bmod 4=1\
i+1 &\text{if } i\bmod 4=2\
0 &\text{if } i\bmod 4=3
\end{cases}
$$
证明可以通过数学归纳或观察二进制规律得到。
那么区间 $[l,r]$ 的异或和可以写成：
$$
l\oplus (l+1)\oplus\dots\oplus r=f®\oplus f(l-1)
$$
因为 $f®=f(l-1)\oplus (l\oplus\dots\oplus r)$。

所以区间异或为 $0$ 等价于：
$$
f®=f(l-1)
$$
令 $L=l-1$，$R=r$，则条件变为：

  • $0\le L\le x-1$
  • $x\le R\le n$
  • $f(L)=f®$

我们需要统计满足上述条件的 $(L,R)$ 对数。
$f(i)$ 的取值只有四种：$i,1,i+1,0$。
但 $i$ 和 $i+1$ 的值随 $i$ 变化，不同 $i$ 难以出现相等。
只有 $0$ 和 $1$ 这两个值会重复出现：

  • $f(i)=0$ 当且仅当 $i\bmod 4=3$；
  • $f(i)=1$ 当且仅当 $i\bmod 4=1$。

$f(i)=i$ 或 $i+1$ 的情况，如果要相等，需要解方程，在 $n$ 很大时只有极少数解，且题目数据范围下可以忽略（实际上仔细分析会发现，$f(L)=f®$ 且 $L\neq R$ 时，$f$ 只能取 $0$ 或 $1$）。
因此我们只需要考虑两种情况：

  • $f(L)=f®=0$；
  • $f(L)=f®=1$。

若 $f=0$：
$f(i)=0\iff i\bmod 4=3$。

  • 左侧 $L\in [0,x-1]$，统计 $\bmod 4=3$ 的个数。
    注意 $L=0$ 时 $f(0)=0$，但 $0\bmod 4=0\neq 3$，需要单独加上。
  • 右侧 $R\in [x,n]$，统计 $\bmod 4=3$ 的个数。

设：

  • $cntL_0=\text{count}(L\in [0,x-1],L\bmod 4=3)+[x>0]$（加一是因为 $L=0$）
  • $cntR_0=\text{count}(R\in [x,n],R\bmod 4=3)$
    则情况一的贡献为 $cntL_0\times cntR_0$。

若 $f=1$：
$f(i)=1\iff i\bmod 4=1$。

  • 左侧 $L\in [0,x-1]$，统计 $\bmod 4=1$ 的个数。
  • 右侧 $R\in [x,n]$，统计 $\bmod 4=1$ 的个数。

设：

  • $cntl=\text{count}(L\in [0,x-1],L\bmod 4=1)$
  • $cntr=\text{count}(R\in [x,n],R\bmod 4=1)$

那么贡献为 $cntl\times cntr$。
因为 $n$ 可达 $10^{18}$，不能线性遍历。
我们需要一个函数work(L,R,r)返回 $[L,R]$ 中模 $4$ 余 $r$ 的整数个数。
实现方法：

  • 找到区间内第一个满足条件的数 $first$：$first=L+((r-L\bmod 4+4)\bmod 4)$
  • 如果 $first > R$，返回 $0$
  • 找到最后一个满足条件的数 $last=R-((R-r)\bmod 4+4)\bmod 4$
  • 个数为 $(last-first)/4+1$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar((x%10)^48);
    }
}
using namespace std;
using namespace FastIO;
const int mod=998244353;
int work(int L,int R,int r){
    if(L>R)return 0;
    int fst=L;
    while(fst<=R&&(fst%4+4)%4!=r)fst++;
    if(fst>R)return 0;
    int las=R;
    while(las>=L&&(las%4+4)%4!=r)las--;
    if(las<fst)return 0;
    return (las-fst)/4+1;
}
int T,n,x;
signed main(){
    read(T);
    while(T--){
        read(n,x);
        int ans=0;
        int cntl=work(0,x-1,3)+(0>=0&&0<=x-1?1:0);
        int cntr=work(x,n,3)+(0>=x&&0<=n?1:0);
        ans=(ans+(cntl%mod)*(cntr%mod)%mod)%mod;
        int numl=work(0,x-1,1),numr=work(x,n,1);
        ans=(ans+(numl%mod)*(numr%mod)%mod)%mod;
        print(ans);puts("");
    }
}