AtCoder Beginner Contest 463 题解

项目	内容
比赛时间	2026-06-20
比赛链接	https://atcoder.jp/contests/abc463
题目数量	A–G 共 7 题

比赛概览

本场整体难度中等偏上。A、B 为简单的签到题；C 题考察"剔除无用信息 + 二分"的观察力；D 题是经典的"二分答案 + 区间调度"贪心；E 题是构造超级源/汇结点后跑 Dijkstra 的经典套路；F 题是一道较难的组合概率题，需要对"冠军候选者"做细致的分类讨论，并配合组合数求和；G 题则是随机游走期望与莫队（Mo's algorithm）的结合，是本场区分度最高、最值得掌握的题目。重点建议掌握 C、D、E 的套路，以及 F、G 的分析方法。

---

A - 16:9

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_a

题目大意

给定图片的宽 $X$ 与高 $Y$（$1 \le X, Y \le 1000$，均为整数），判断宽高比是否为 $16:9$，即 $X:Y = 16:9$。若成立输出 Yes，否则输出 No。

思路

由比例的性质，$X:Y = 16:9$ 等价于

$$\frac{X}{16} = \frac{Y}{9}.$$

交叉相乘去分母，得到

$$9X = 16Y.$$

注意：

• 直接使用浮点数判断 $\frac{X}{Y} = \frac{16}{9}$ 可能引入精度误差；两边同时乘以 $Y \cdot 9$ 后化为整数比较则完全精确。
• 由于 $X, Y \le 1000$，$9X$ 与 $16Y$ 最大不超过 $16000$，用 int 或 long long 均可。

因此只需判断 9 * X == 16 * Y 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long X, Y;
    cin >> X >> Y;
    cout << (9 * X == 16 * Y ? "Yes" : "No") << '\n';
    return 0;
}

官方题解同时给出了等价的核心代码：

X, Y = map(int, input().split())
if X * 9 == Y * 16:
    print("Yes")
else:
    print("No")

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

B - Train Reservation

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_b

题目大意

有 $N$ 列列车，每列有 A、B、C、D、E 五个座位列。给出每列列车的座位空缺情况字符串 $S_i$（长度为 $5$，由 o/x 组成，第 $1\sim5$ 个字符分别对应 A$\sim$E 列）。给定目标座位列 $X \in \{A,B,C,D,E\}$，判断是否存在至少一列列车在 $X$ 列有空位。若存在输出 Yes，否则输出 No。

思路

逐一检查每列列车即可。将列名 $X$ 转化为下标：

$$idx = X - \texttt{'A'},$$

也就是 $A \to 0, B \to 1, \ldots, E \to 4$。对每行字符串 $S_i$，只需判断 S_i[idx] == 'o'。一旦找到任何一个 o，答案即为 Yes。

这是最朴素的线性扫描，$N \le 100$ 完全够用。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    char X;
    cin >> N >> X;
    int idx = X - 'A';
    bool ok = false;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        if (s[idx] == 'o') ok = true;
    }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

官方题解给出的 Python 参考代码：

N, X = input().split()
N = int(N)
X = ord(X) - ord('A')
S = [input() for _ in range(N)]
ans = False
for s in S:
    ans |= s[X] == "o"
if ans:
    print("Yes")
else:
    print("No")

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$（不计输入存储，或 $O(N)$ 若存储全部字符串）

---

C - Tallest at the Moment

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_c

题目大意

会议室中有 $N$ 个人，第 $i$ 个人身高为 $H_i$，将于 $L_i$ 分钟后离开且不再回来，其中 $L_1 \le L_2 \le \cdots \le L_N$。有 $Q$ 个询问，第 $i$ 个询问给出整数 $T_i$，求 $T_i + \frac12$ 分钟后仍在会议室的人中的最高身高。题目保证每个询问时刻都至少有一人在会议室。

思路

关键观察（剔除无用的人）。 若两个人满足"一个更高、且离开得更晚"，即存在 $i, j$ 使得

$$H_i \ge H_j \quad \text{且} \quad L_i \ge L_j,$$

那么在任意时刻，只要 $j$ 还在会议室（$t < L_j$），$i$ 也一定还在会议室（因为 $L_i \ge L_j$），并且 $i$ 的身高不矮于 $j$。因此 $j$ 在任意时刻都不可能成为"最高的人"，从会议室中把它"剔除"不会影响任何询问的答案。

由于输入已经按 $L$ 非降序给出，我们可以用单调栈在线地完成剔除：

• 依次处理每个人 $(H, L)$；
• 只要栈顶元素的身高 $\le H$（即栈顶那个人更矮、且离开得不比当前人晚，被当前人"支配"），就弹出它；
• 把 $(H, L)$ 压入栈。

经过这一处理，栈中元素满足：身高严格递减，离开时间非递减。

回答询问。 注意 $L_i$ 为整数，因此在 $T + \frac12$ 时刻第 $i$ 个人仍在会议室当且仅当

$$L_i > T + \frac12 \iff L_i \ge T + 1 \iff L_i > T.$$

由于栈中 $L$ 非递减，$L > T$ 的人构成栈的一个后缀（即栈中第一个满足 $L > T$ 的人及其后面的所有人）。又因为栈中身高严格递减，所以这个后缀的第一个元素——也就是 $L > T$ 的人中最早进栈的那个——就是答案（它最高）。用二分（upper_bound 找第一个 $L > T$ 的位置）即可 $O(\log N)$ 回答每个询问。

为什么可行？ 弹出条件保证相邻元素身高严格递减；又因为输入按 $L$ 非降序处理、且只会在栈顶压入，栈中 $L$ 保持非递减。这两条性质正是回答询问所需要的：$L$ 非递减保证"仍在会议室"的人是栈的一个后缀（可二分定位），身高递减保证该后缀的第一个元素就是当前最高的人。

另一种等价视角（更直观的解法）：因为 $L$ 单调不减，$T + \frac12$ 时刻仍在会议室的人恰好是原序列的一个后缀，先用后缀 $\max$ 预处理，再二分定位分界点。两种做法的本质相同，栈做法相当于预先压缩了序列。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<long long, long long>> st;   // (H, L)，处理后 H 严格递减、L 非递减
    for (int i = 0; i < N; i++) {
        long long H, L;
        cin >> H >> L;
        while (!st.empty() && st.back().first <= H) st.pop_back(); // 被支配的人先走
        st.push_back({H, L});
    }

    vector<long long> Ls;                    // 只存 L，用于二分
    for (auto &p : st) Ls.push_back(p.second);

    int Q;
    cin >> Q;
    while (Q--) {
        long long T;
        cin >> T;
        int j = upper_bound(Ls.begin(), Ls.end(), T) - Ls.begin(); // 第一个 L > T 的人
        cout << st[j].first << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N + Q \log N)$（构造栈 $O(N)$，每个询问二分 $O(\log N)$）
• 空间复杂度：$O(N)$

---

D - Maximize the Gap

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_d

题目大意

数轴上有 $N$ 块布，第 $i$ 块覆盖闭区间 $[L_i, R_i]$（$0 \le L_i < R_i \le 10^9$）。两块布"重叠"当且仅当存在某个点同时被两者覆盖（在端点相交也算重叠）。对两块不重叠的布，定义它们的距离为

$$\min_{p \in \text{布一}, q \in \text{布二}} |p - q|.$$

选出 $K$ 块两两不重叠的布，其得分定义为所有两两距离中的最小值。求最大可能得分；若无法选出 $K$ 块两两不重叠的布，输出 -1。

思路

问题转化。 设两块布 $[L_i, R_i]$、$[L_j, R_j]$ 不重叠且 $R_i < L_j$（即 $i$ 在 $j$ 左边），则距离为 $L_j - R_i$。若把选出的布按右端点从左到右排好，则两两距离的最小值就等于相邻两块之间的距离的最小值（非相邻的间距只会更大）。因此问题变成：

能否选出 $K$ 块布，使排序后相邻两块满足 $L_{next} - R_{prev} \ge d$，即 $R_{prev} + d \le L_{next}$？

二分答案 $d$。 可行性随 $d$ 增大而单调变差，所以可以二分最大的 $d$。

贪心判断可行性（区间调度）。 将所有布按右端点 $R$ 升序排序，维护变量 last 表示上一块被选中布的右端点，初始为 $-\infty$。按顺序扫描：

• 若当前布满足 $last + d \le L_i$（即与前一块的间距至少为 $d$），就选中它并令 last = R_i；
• 否则跳过。

记选中的块数为 cnt，则 cnt >= K 即可行。

贪心正确性。 这是经典区间调度贪心：总是选择"结束最早且可行的"区间。假设贪心选出的第一块是 $j$，任意一个可行方案选出的第一块是 $j^*$。由于按 $R$ 升序扫描，$R_j \le R_{j^*}$；把可行方案中的 $j^*$ 替换成 $j$，后续区间只需要满足 $L \ge R_{j^*} + d$，而 $R_j \le R_{j^*}$，所以替换后依然可行，选择个数不减少。归纳可知贪心得到的选择数最大。而"最大选择数 $\ge K$"正是"能选出 $K$ 块间距 $\ge d$ 的布"的充要条件。

判定无解。 当 $d = 1$ 都不可行时（即连 $K$ 块两两不重叠的布都选不出来），输出 -1。注意 $d \ge 1$ 意味着 $L_{next} - R_{prev} \ge 1$，即 $L_{next} > R_{prev}$，这正是"严格不重叠"（在端点重合也算重叠，故必须严格大于）。

边界情况。 $K = N$ 时只有全选一种可能，需检查这 $N$ 块是否两两间距 $\ge d$；二分框架天然覆盖。所有值使用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<pair<long long, long long>> a(N);
    for (int i = 0; i < N; i++) cin >> a[i].first >> a[i].second;

    // 按右端点排序
    sort(a.begin(), a.end(), [](auto &x, auto &y) { return x.second < y.second; });

    // 判断能否选出 K 块，使得相邻间距 >= d
    auto ok = [&](long long d) {
        long long last = -(1LL << 60);   // 上一块被选中布的右端点，初始为 -inf
        int cnt = 0;
        for (auto &[L, R] : a) {
            if (last + d <= L) {          // 与前一块的间距至少为 d
                cnt++;
                last = R;
            }
        }
        return cnt >= K;
    };

    if (!ok(1)) {                         // 连 K 块互不重叠的布都选不出
        cout << -1 << '\n';
        return 0;
    }

    long long lo = 1, hi = 2000000000LL, ans = 1;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (ok(mid)) ans = mid, lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N + N \log A)$，其中 $A$ 为二分上界（$10^9$ 量级），即约 $O(N \log 10^9)$
• 空间复杂度：$O(N)$

---

E - Roads and Gates

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_e

题目大意

有 $N$ 个城市和 $M$ 条双向道路，第 $i$ 条道路连接 $u_i, v_i$，通行耗时 $T_i$ 分钟。此外每个城市都装有传送门：从城市 $i$ 传送到城市 $j$ 需要 $X_i + X_j + Y$ 分钟（$Y$ 为全局常量）。同一城市内换乘不花时间。对每个 $k = 2, 3, \ldots, N$，求从城市 $1$ 到城市 $k$ 的最短时间。答案可能超过 $2^{31}$。

思路

问题转化。 关键在于把"传送门"这种两点之间的任意连通改写成普通图的边。观察传送代价：

$$X_i + X_j + Y,$$

它可以拆成三段：$i \to$（传送起点）花费 $X_i$，中间花费 $Y$，（传送终点）$\to j$ 花费 $X_j$。于是我们引入两个超级结点 $W_S$ 和 $W_T$：

• 对每个城市 $i$，加有向边 $i \to W_S$，权值为 $X_i$；
• 加有向边 $W_T \to i$，权值为 $X_i$；
• 加有向边 $W_S \to W_T$，权值为 $Y$。

那么任意一次"从 $i$ 传送到 $j$"恰好对应路径 $i \to W_S \to W_T \to j$，总代价恰为 $X_i + Y + X_j$。原题的所有旅行方式（道路或传送门）都变成新图上的有向/无向边。

注意 $W_S$ 只有一条出边指向 $W_T$，$W_T$ 只出边指向各城市，因此不会产生无意义的环路；多次使用传送门等价于多次经过 $W_S \to W_T$ 这条边，最短路径上不会重复绕圈。

求解。 新图共有 $N + 2$ 个结点、$M + 2N + 1$ 条边，从城市 $1$ 出发跑 Dijkstra 即可。由于边权为正，Dijkstra 是正确的。

注意： 最短路径可能达到 $3 \times 10^9$（样例 2 即如此），必须使用 64 位整数（long long）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long Y;
    cin >> N >> M >> Y;

    vector<vector<pair<int, long long>>> g(N + 2);   // 0..N-1 为城市，N = W_S，N+1 = W_T
    for (int i = 0; i < M; i++) {
        int u, v;
        long long T;
        cin >> u >> v >> T;
        --u; --v;
        g[u].push_back({v, T});
        g[v].push_back({u, T});
    }

    for (int i = 0; i < N; i++) {
        long long X;
        cin >> X;
        g[i].push_back({N, X});        // 城市 i -> W_S，权值 X_i
        g[N + 1].push_back({i, X});    // W_T -> 城市 i，权值 X_i
    }
    g[N].push_back({N + 1, Y});        // W_S -> W_T，权值 Y

    const long long INF = (1LL << 62);
    vector<long long> dist(N + 2, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[0] = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int k = 1; k < N; k++) cout << dist[k] << (k == N - 1 ? '\n' : ' ');
    return 0;
}

复杂度分析

• 时间复杂度：$O((N + M) \log N)$
• 空间复杂度：$O(N + M)$

---

F - Senshuraku

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_f

题目大意

$2N$ 名选手即将进行最后的 $N$ 场比赛，第 $i$ 场由第 $2i-1$ 与第 $2i$ 名选手对阵，每场两人胜率各为 $\frac12$。比赛前选手 $i$ 已获胜 $A_i$ 场。全部结束后，从胜场最多的人中等概率随机选出一名冠军。对每名选手，求其成为冠军的概率，对 $998244353$ 取模后输出。

思路

本题信息量大，关键在于细致的分类与组合计数。

观察 1：谁还有机会。 每名选手在最后 $N$ 场中最多赢 $1$ 场，因此最终胜场为 $A_i$ 或 $A_i + 1$。设

$$W = \max_{1 \le i \le 2N} A_i,$$

则冠军的胜场只能是 $W$ 或 $W+1$。于是 $A_i \le W - 2$ 的选手最终至多 $W-1$ 胜，永远不可能成为候选者，可以把他们的胜场数当作 $0$ 处理（不影响任何概率）。

观察 2：对局分类。 修改后每场对局双方的胜场数只可能是 $W, W-1, 0$ 中的值。把每场对局按双方胜场数排序成 $(L, R)$（$L \le R$）后分为 6 类，数量记为 $m_0 \sim m_5$：

类别	双方胜场	含义
$m_0$	$(W, W)$	两名 $W$ 胜选手对局
$m_1$	$(W-1, W)$	$W-1$ 胜与 $W$ 胜对局
$m_2$	$(0, W)$	$0$ 胜与 $W$ 胜对局
$m_3$	$(W-1, W-1)$	两名 $W-1$ 胜对局
$m_4$	$(0, W-1)$	$0$ 胜与 $W-1$ 胜对局
$m_5$	$(0, 0)$	两名 $0$ 胜对局

统一框架。 固定"冠军胜场"为 $C \in \{W, W+1\}$。称最终胜场恰好等于 $C$ 的人为候选者。对某一类对局，其结果要么产生若干候选者，要么导致"矛盾"（即某人的胜场超过了 $C$，使得最大胜场不可能是 $C$）。逐类分析后，每类对局必属于下列两种之一：

• 类型一：以概率 $\frac12$ 产生恰好 $1$ 名候选者，否则产生 $0$ 名；
• 类型二：以概率 $p$ 产生 $k$ 名候选者（$k \ge 0$），以概率 $1-p$ 矛盾。

设所有类型二对局的 $p$ 之积为 $P$、$k$ 之和为 $K$，类型一对局的数量为 $x$。则在"不矛盾"的条件下，候选者总数为 $K$ 加上类型一对局中"成功"的次数，取值范围是 $[K, K+x]$。

• 对参与某场类型一对局的玩家：包含该玩家且候选者总数为 $w$ 的概率为

$$P \cdot \frac{\binom{x-1}{w-K-1}}{2^{x}}, \qquad K+1 \le w \le K+x.$$

推导：该玩家必须"成功"（概率 $\frac12$，已经算在分母 $2^x$ 中），其余 $x-1$ 场类型一对局中恰有 $w-K-1$ 场成功。

• 对参与某场类型二对局的玩家：包含该玩家且候选者总数为 $w$ 的概率为

$$qP \cdot \frac{\binom{x}{w-K}}{2^{x}}, \qquad K \le w \le K+x,$$

其中 $q$ 是"在不矛盾的前提下该玩家恰好达到 $C$ 胜"的条件概率。

得到上述概率后，该玩家成为冠军的概率就是把 $\Pr(\text{含该玩家且总数为 } w) \times \frac1w$ 对 $w$ 求和。

下面分两种情况具体化。

情况一：冠军胜场为 $W+1$。

此时候选者 = 初始 $W$ 胜且赢下自己对局的玩家。

• $m_1$、$m_2$ 类（$W$ 胜方赢则达到 $W+1$）是类型一对局，$x = m_1 + m_2$；
• $m_0$ 类：$W$ 对 $W$，无论谁赢都恰好产生 $1$ 名候选者，属类型二，$p = 1, k = 1$；
• $m_3, m_4, m_5$ 类：不可能有人达到 $W+1$，属类型二，$p = 1, k = 0$。

所以 $P = 1$，$K = m_0$，候选者总数 $w \in [m_0, m_0 + m_1 + m_2]$。

• $m_0$ 类中的某玩家：成为候选者需赢下对局（概率 $\frac12$），其余 $m_1+m_2$ 场类型一对局独立地以 $\frac12$ 产生候选者，故

$$\Pr(\text{含该玩家且总数为 } w) = \frac{\binom{m_1+m_2}{w - m_0}}{2^{m_1+m_2+1}}.$$

• $m_1$、$m_2$ 类中初始 $W$ 胜的玩家：需赢下对局，其余 $m_1+m_2-1$ 场类型一对局中有 $w - m_0 - 1$ 场成功，故

$$\Pr(\text{含该玩家且总数为 } w) = \frac{\binom{m_1+m_2-1}{w - m_0 - 1}}{2^{m_1+m_2}}.$$

情况二：冠军胜场为 $W$。

此时若存在 $m_0$ 类对局（$W$ 对 $W$），必产生一名 $W+1$ 胜者，冠军胜场不可能为 $W$，故仅当 $m_0 = 0$ 时考虑。

• $m_4$ 类是类型一对局，$x = m_4$；
• $m_1$ 类：$W-1$ 方获胜时，该玩家达到 $W$，而 $W$ 方保持 $W$，两人都成为候选者（$k=2$，$p=\frac12$）；$W$ 方获胜则产生 $W+1$，矛盾；
• $m_2$ 类：$W$ 方获胜则矛盾，$0$ 方获胜则 $W$ 方保持 $W$ 成为唯一候选者（$k=1$，$p=\frac12$）；
• $m_3$ 类：两名 $W-1$ 选手对局，胜者达到 $W$，恰好 $1$ 名候选者（$p=1, k=1$）；
• $m_5$ 类：无候选者（$p=1, k=0$）。

于是

$$K = 2m_1 + m_2 + m_3, \qquad P = 2^{-(m_1+m_2)}, \qquad x = m_4,$$

候选者总数 $w \in [K, K + m_4]$。

• $m_1$ 类中双方玩家：不矛盾时（$W-1$ 方获胜）两人都成为候选者，$q = 1$：

$$\Pr = \frac{\binom{m_4}{w-K}}{2^{m_1+m_2+m_4}}.$$

• $m_2$ 类中初始 $W$ 胜的玩家：同理 $q = 1$，公式同上；
• $m_3$ 类中的某玩家：需赢下对局，$q = \frac12$：

$$\Pr = \frac12 \cdot \frac{\binom{m_4}{w-K}}{2^{m_1+m_2+m_4}};$$

• $m_4$ 类中初始 $W-1$ 胜的玩家：需赢下对局（$\frac12$），其余 $m_4 - 1$ 场类型一对局中有 $w - K - 1$ 场成功：

$$\Pr = \frac{\binom{m_4-1}{w-K-1}}{2^{m_1+m_2+m_4}}, \qquad K+1 \le w \le K + m_4.$$

实现要点。 预计算 $0 \sim 2N$ 的阶乘与阶乘逆元，即可 $O(1)$ 求组合数 $\binom{n}{r}$、$\frac1w$ 以及 $2^{-k}$。两类情况下对 $w$ 的循环总长度都是 $O(N)$。最后按每场对局把对应概率输出给双方。

参考代码

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

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    int M2 = 2 * N;

    // 阶乘 / 阶乘逆元
    vector<ll> fact(M2 + 1), ifact(M2 + 1);
    fact[0] = 1;
    for (int i = 1; i <= M2; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[M2] = modpow(fact[M2], MOD - 2);
    for (int i = M2; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;

    auto C = [&](int n, int r) -> ll {
        if (r < 0 || r > n) return 0;
        return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    };
    auto inv = [&](int n) -> ll {           // 1 / n
        return ifact[n] * fact[n - 1] % MOD;
    };

    vector<pair<int, int>> match(N);
    int W = 0;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        match[i] = {a, b};
        W = max({W, a, b});
    }

    // 分类：0..5 对应 m_0..m_5
    auto type = [&](int L, int R) -> int {
        if (L > R) swap(L, R);
        if (R == W) {
            if (L == W) return 0;
            if (L + 1 == W) return 1;
            return 2;
        }
        if (R + 1 == W) {
            if (L + 1 == W) return 3;
            return 4;
        }
        return 5;
    };

    ll cnt[6] = {0, 0, 0, 0, 0, 0};
    for (auto &[a, b] : match) cnt[type(a, b)]++;

    ll inv2 = (MOD + 1) / 2;
    ll prob[6][2] = {{0}};   // prob[t][0] 给胜场多者, prob[t][1] 给胜场少者

    // 情况一：冠军胜场为 W+1
    {
        ll mn = cnt[0], mx = cnt[0] + cnt[1] + cnt[2];
        ll coef = modpow(modpow(2, cnt[1] + cnt[2]), MOD - 2);  // 1 / 2^(m1+m2)
        if (mn) {
            for (int w = mn; w <= mx; w++) {
                ll p = C(cnt[1] + cnt[2], w - mn) * coef % MOD * inv(w) % MOD;
                prob[0][0] = (prob[0][0] + p * inv2) % MOD;
                prob[0][1] = (prob[0][1] + p * inv2) % MOD;
            }
        }
        for (int w = mn + 1; w <= mx; w++) {
            ll p = C(cnt[1] + cnt[2] - 1, w - mn - 1) * coef % MOD * inv(w) % MOD;
            prob[1][0] = (prob[1][0] + p) % MOD;   // W 胜方
            prob[2][0] = (prob[2][0] + p) % MOD;   // W 胜方
        }
    }

    // 情况二：冠军胜场为 W（仅当 m_0 = 0 时可行）
    if (cnt[0] == 0) {
        ll mn = 2 * cnt[1] + cnt[2] + cnt[3];
        ll mx = mn + cnt[4];
        ll coef = modpow(modpow(2, cnt[1] + cnt[2] + cnt[4]), MOD - 2);
        if (mn) {
            for (int w = mn; w <= mx; w++) {
                ll p = C(cnt[4], w - mn) * coef % MOD * inv(w) % MOD;
                prob[1][0] = (prob[1][0] + p) % MOD;
                prob[1][1] = (prob[1][1] + p) % MOD;
                prob[2][0] = (prob[2][0] + p) % MOD;
                prob[3][0] = (prob[3][0] + p * inv2) % MOD;
                prob[3][1] = (prob[3][1] + p * inv2) % MOD;
            }
        }
        for (int w = mn + 1; w <= mx; w++) {
            ll p = C(cnt[4] - 1, w - mn - 1) * coef % MOD * inv(w) % MOD;
            prob[4][0] = (prob[4][0] + p) % MOD;
        }
    }

    for (int i = 0; i < N; i++) {
        int L = match[i].first, R = match[i].second;
        int t = type(L, R);
        if (L < R) cout << prob[t][1] << " " << prob[t][0] << " ";
        else       cout << prob[t][0] << " " << prob[t][1] << " ";
    }
    cout << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$（阶乘预计算 $O(N)$，两类情况对 $w$ 的求和总计 $O(N)$）
• 空间复杂度：$O(N)$

---

G - Random Walk Distance

题目链接：https://atcoder.jp/contests/abc463/tasks/abc463_g

题目大意

Takahashi 从数轴原点出发，进行 $N$ 次移动：每次等概率地向左或向右移动 $1$ 个单位，各次移动独立。设最终坐标为 $x'$。给定 $T$ 组询问 $(N, X)$，求 $E[|x' - X|]$ 对 $998244353$ 取模的值。

思路

分布。 $N$ 步后若向右走了 $i$ 步，则坐标

$$x' = i - (N - i) = 2i - N,$$

且

$$P(x' = 2i - N) = \frac{1}{2^N}\binom{N}{i}, \qquad i = 0, 1, \ldots, N.$$

由对称性 $E[x'] = 0$，且 $|x'| \le N$ 恒成立。

简单情形 $|X| \ge N$。 若 $X \ge N$，则 $x' - X \le N - X \le 0$，所以 $|x' - X| = X - x'$，期望为

$$E[X - x'] = X - E[x'] = X.$$

同理若 $X \le -N$，期望为 $-X$。

一般情形 $-N < X < N$。 记 $M = \left\lceil \dfrac{N+X}{2} \right\rceil$。利用恒等式

$$|X - x'| = (x' - X) + 2(X - x')\mathbf 1\{x' < X\},$$

其中 $\mathbf 1\{\cdot\}$ 为指示函数，而条件 $x' < X \iff 2i - N < X \iff i < \frac{N+X}{2} \iff i \le M-1$。于是

$$\begin{aligned} E[|X - x'|] &= E[x'] - X + 2\sum_{i=0}^{M-1} (X - (2i - N))\,P(x' = 2i - N) \\ &= -X + \frac{1}{2^{N-1}}\sum_{i=0}^{M-1} (N + X - 2i)\binom{N}{i}. \end{aligned}$$

定义

$$f(N, M) = \sum_{i=0}^{M-1}\binom{N}{i}, \qquad g(N, M) = \sum_{i=0}^{M-1} i\binom{N}{i},$$

则答案写为

$$E[|x'-X|] = -X + \frac{(N+X)\,f(N,M) - 2g(N,M)}{2^{N-1}}.$$

快速计算 $f, g$：莫队算法。 直接对每个询问求前缀和太慢；但 $f, g$ 在二维网格 $(N, M)$ 上相邻点之间可以 $O(1)$ 转移。利用组合恒等式 $\binom{N+1}{i} = \binom{N}{i} + \binom{N}{i-1}$：

$$\begin{aligned} f(N, M+1) &= f(N, M) + \binom{N}{M}, \\ f(N+1, M) &= 2f(N, M) - \binom{N}{M-1}, \\ g(N, M+1) &= g(N, M) + M\binom{N}{M}, \\ g(N+1, M) &= 2g(N, M) + f(N, M) - M\binom{N}{M-1}. \end{aligned}$$

由后两式反解即可得到 $N$ 减小、$M$ 减小的转移。约定 $\binom{n}{k} = 0$（当 $k > n$），则上述递推在"越界"的临时状态（如 $M > N$）下依然成立。

把所有询问按 $M = \lceil\frac{N+X}{2}\rceil$ 转为平面上的点 $(N, M)$，用莫队按"$N$ 所在块"排序，指针 $(N, M)$ 在相邻询问间移动，每次移动 $O(1)$。取块大小 $B \approx \frac{N_{\max}}{\sqrt T}$ 时，总移动次数

$$O\!\left(\frac{N_{\max}^2}{B} + T B\right) = O(N_{\max}\sqrt{T}),$$

可以承受。

模运算。 预计算阶乘与阶乘逆元实现 $O(1)$ 组合数；最后把 $(N+X)f - 2g$ 乘以 $2^{-(N-1)}$（预计算 $2$ 的负幂）并减 $X$。注意 $X$ 可为负，需要正确取模。

边界： $|X| \ge N$ 的询问不进入莫队，直接输出 $|X|$。

参考代码

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

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    vector<pair<int, int>> queries(T);   // (N, X)
    int maxN = 0;
    for (int i = 0; i < T; i++) {
        int N, X;
        cin >> N >> X;
        queries[i] = {N, X};
        maxN = max(maxN, N);
    }

    // 阶乘 / 阶乘逆元（用于 O(1) 组合数）
    vector<ll> fact(maxN + 1), ifact(maxN + 1);
    fact[0] = 1;
    for (int i = 1; i <= maxN; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[maxN] = modpow(fact[maxN], MOD - 2);
    for (int i = maxN; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;

    auto C = [&](int n, int k) -> ll {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
    };

    // 2 的幂与 2 的负幂
    vector<ll> ipow2(maxN + 1);
    ipow2[0] = 1;
    ll inv2 = (MOD + 1) / 2;
    for (int i = 1; i <= maxN; i++) ipow2[i] = ipow2[i - 1] * inv2 % MOD;

    // 构造莫队询问
    struct Q {
        int n, m, id;
    };
    vector<Q> qs;
    vector<ll> ans(T);
    for (int i = 0; i < T; i++) {
        int N = queries[i].first, X = queries[i].second;
        if (X >= N) { ans[i] = X % MOD; continue; }
        if (X <= -N) { ans[i] = (-(ll)X) % MOD; continue; }
        int m = (N + X + 1) / 2;           // ceil((N+X)/2)
        qs.push_back({N, m, i});
    }

    int B = max(1, (int)(maxN / sqrt((double)max(1, T)) + 1));
    sort(qs.begin(), qs.end(), [&](const Q &a, const Q &b) {
        int ba = a.n / B, bb = b.n / B;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? a.m > b.m : a.m < b.m;
    });

    // 当前状态 (n, m) 对应的 f, g
    ll f = 0, g = 0;
    int n = 0, m = 0;

    auto incN = [&]() {   // (n, m) -> (n+1, m)
        ll c = C(n, m - 1);
        ll nf = (2 * f - c) % MOD;
        ll ng = (2 * g + f - (ll)m * c) % MOD;
        if (nf < 0) nf += MOD;
        if (ng < 0) ng += MOD;
        f = nf; g = ng; ++n;
    };
    auto decN = [&]() {   // (n, m) -> (n-1, m)
        --n;
        ll c = C(n, m - 1);
        ll nf = (f + c) * inv2 % MOD;
        ll ng = (g - nf + (ll)m * c) % MOD;
        ng = (ng % MOD + MOD) % MOD * inv2 % MOD;
        f = nf; g = ng;
    };
    auto incM = [&]() {   // (n, m) -> (n, m+1)
        ll c = C(n, m);
        f = (f + c) % MOD;
        g = (g + (ll)m * c) % MOD;
        ++m;
    };
    auto decM = [&]() {   // (n, m) -> (n, m-1)
        --m;
        ll c = C(n, m);
        f = (f - c) % MOD;
        g = (g - (ll)m * c) % MOD;
        if (f < 0) f += MOD;
        if (g < 0) g += MOD;
    };

    for (auto &q : qs) {
        while (n < q.n) incN();
        while (n > q.n) decN();
        while (m < q.m) incM();
        while (m > q.m) decM();

        int X = queries[q.id].second;
        ll term = ((ll)(q.n + X) % MOD * f % MOD - 2 * g % MOD + MOD) % MOD;
        ll xmod = (X % MOD + MOD) % MOD;
        ans[q.id] = (term * ipow2[q.n - 1] % MOD - xmod + MOD) % MOD;
    }

    for (int i = 0; i < T; i++) cout << ans[i] << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N_{\max}\sqrt{T})$，其中 $N_{\max} = \max N$（莫队总移动量）
• 空间复杂度：$O(N_{\max} + T)$