题解 CF2225D Exceptional Segments

zsz_qaq · 2026-04-25 19:00:25 · 题解

前言

才发现CF题也能写题解。

分析

给定两个整数 n 和 x，考虑序列 [1, 2, 3, \ldots, n]，需要找出包含 x 且异或和为 0 的子段数目。子段 [l, r] 需满足 1 \leq l \leq x \leq r \leq n 且 l \oplus (l + 1) \oplus \dots \oplus r = 0。

前缀异或和的性质

定义前缀异或和 pre[i] = 1 \oplus 2 \oplus \dots \oplus i，则子段 [l, r] 的异或和为 pre[r] \oplus pre[l - 1]。因此，问题转化为找到满足 pre[r] = pre[l - 1] 且 l - 1 < x \leq r 的 (l-1, r) 对的数目。

通过观察前缀异或和的规律，发现其具有周期性，周期为 4：

• 当 i \equiv 0 \pmod 4 时，pre[i] = i；
• 当 i \equiv 1 \pmod 4 时，pre[i] = 1；
• 当 i \equiv 2 \pmod 4 时，pre[i] = i + 1；
• 当 i \equiv 3 \pmod 4 时，pre[i] = 0。

此外，pre[0] = 0（定义前缀异或和的初始值为 0）。

关键

由于前缀异或和的周期性，只有两种情况可能存在多个 i 使得 pre[i] 相同：

1. pre[i] = 0$：对应 $i = 0 \ / \ i \equiv 3 \pmod 4
2. pre[i] = 1$：对应 $i \equiv 1 \pmod 4

其他情况下，pre[i] 的值唯一，不会产生重复。

统计方法

我们需要统计以下四个量：

其中：

代码实现

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

ll f(ll a) {
    if (a >= 0) {
        return a / 4;
    } else {
        return (a - 3) / 4;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, x;
        cin >> n >> x;
        ll cnta1 = f(x - 2) + 1, cnta0 = f(x - 4) + 1;
        ll cntb1 = f(n - 1) - f(x - 2), cntb0 = f(n - 0) - f(x - 4);
        ll ans = (((cnta1 % mod) * (cntb1 % mod)) % mod + ((cnta0 % mod) * (cntb0 % mod)) % mod) % mod;
        ans = (ans + (cntb0 % mod)) % mod;
        if (ans < 0) {
            ans += mod;
        }
        cout << ans << endl;
    }
    return 0;
}