题意

考虑一个 [1,2,3,…,n] 的序列和数 x，你需要找到有多少个数对 (l,r) 使得：

1≤l≤x≤r≤n；
⨁i=lr​i=0。

n,x≤1018
原题：https://codeforces.com/contest/2225/problem/D

我们考虑枚举几个样例 找规律：
如8以内的XOR为0的序列有：

1 2 3 
1 2 3 4 5 6 7 
2 3 4 5 
4 5 6 7 
4

有点意思 拓展下范围呢:

1 2 3 
1 2 3 4 5 6 7 
1 2 3 4 5 6 7 8 9 10 11 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
2 3 4 5 
2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 10 11 12 13 
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
4 5 6 7 
4 5 6 7 8 9 10 11 
4 5 6 7 8 9 10 11 12 13 14 15 
6 7 8 9 
6 7 8 9 10 11 12 13 
6 7 8 9 10 11 12 13 14 15 16 17 
...

发现从每个偶数开始的序列 每4个的XOR为0
从1开始的序列 因为有1的存在 所以要再xor掉一个1
如 2xor3 =1 4xor5 = 1

我们其实有2个经典结论：
记Sn为前n项的XOR
1.

nmod4=0⟺Sn​=n
nmod4=1⟺Sn​=1
nmod4=2⟺Sn​=n+1
nmod4=3⟺Sn​=0

2.

    XOR(l,r) == Sr XOR S(l-1)

可以记到板子上 不过其实按上面的数据找规律也能找到

发现 经典结论中 只有0 和 1 是可以重复的 也就是对于任意的(n,n+4)都至少有一个0和一个1

那么这个题就转化为了 找一对(l,r)
使得Sl == Sr

AC Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;

int get0(int x){
    if(x>=3){
        return 2LL+(x-3)/4;
    }else{
        return 1LL;
    }
}
int get1(int x){
    if(x>=1){
        return 1LL+(x-1)/4;
    }else{
        return 0LL;
    }
}
void solve() {
    int n,x;
    cin>>n>>x;  
    int l = get0(x-1)%mod;
    int r = (get0(n)-l)%mod;
    int ans = l*r;
    l = get1(x-1)%mod;
    r = (get1(n)-l)%mod;
    ans += l*r;
    ans%= mod;
    cout<<ans<<endl;

}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}