AtCoder Beginner Contest 450 题解

for-each2026年8月18日大约 19 分钟

AtCoder Beginner Contest 450 题解

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

比赛概览

本场比赛的题目难度从 A 的纯输出签到题一路爬升到 G 的期望与生成函数类推导题。A、B 是基础送分题，C 是经典的连通块计数（BFS/DFS 或并查集），D 题的关键在于发现"加 $K$ 与减 $K$ "等价（在平移意义下），从而转化为对余数序列做循环滑窗，是本场第一个有区分度的题。E 题考察 Fibonacci 字符串的前缀性质与递归计数。F 题需要把"强连通"条件化简成"从 1 能到达 N"，再用 DP + 懒标记线段树优化，是本场的核心难题之一。G 题则综合了期望的线性性与系数对称性，通过一个巧妙的递推计算任意两元素符号乘积的期望，值得重点掌握。

A - 3,2,1,GO

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_a

题目大意

给定正整数 $N$ （ $1 \le N \le 9$ ），按从大到小的顺序输出 $N, N-1, \dots, 1$ ，数与数之间用逗号 , 分隔。

思路

题目要求非常直接：从 $N$ 循环到 $1$ ，每输出一个数，若它不是最后一个数 $1$ ，就再输出一个逗号。这里唯一需要注意的边界情况是末尾不能有多余的逗号，因此逗号要么在所有数之前输出，要么在除最后一个以外的每个数之后输出。实现上可以用 if (i != 1) 判断当前输出的数字是否为 $1$ 来避免尾部逗号。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    for (int i = N; i >= 1; i--) {
        cout << i;
        if (i != 1) cout << ',';
    }
    cout << '\n';
    return 0;
}

官方题解还给出了用 Python 的 join 一行完成的写法，这里一并附上：

N = int(input())
print(",".join(str(i) for i in range(N, 0, -1)))

复杂度分析

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

B - Split Ticketing

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_b

题目大意

有 $N$ 个车站 $1, 2, \dots, N$ 自西向东排成一条直线。对任意 $1 \le i < j \le N$ ，从车站 $i$ 上车、车站 $j$ 下车的票价是 $C_{i,j}$ 。问是否存在三个整数 $a < b < c$ ，使得"先买 $a \to b$ 、再买 $b \to c$ "的两张票总价严格小于直达票 $a \to c$ 的票价，即

C_{a,b} + C_{b,c} < C_{a,c}.

思路

这道题几乎是把判定条件原封不动地给了出来， $N \le 100$ 说明我们可以放心地三重枚举所有三元组 $(a,b,c)$ ：

O\left(\binom{N}{3}\right) = O(N^3) \le 10^6,

完全在时间限制内。实现时先把输入的三角矩阵读入二维数组 $C[i][j]$ （第 $i$ 行输入的是 $C_{i,i+1}, \dots, C_{i,N-1}$ ，即只读 $j > i$ 的部分），然后枚举 $0 \le a < b < c \le N-1$ 检查不等式即可。

两点注意：一是 $C_{i,j}$ 最大可达 $10^9$ ，两者相加可达 $2 \times 10^9$ ，超过 32 位有符号整数上限，因此建议用 long long 存储；二是找到一组合法三元组后即可直接输出 Yes 并结束程序，避免继续无意义的循环。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<ll>> C(N, vector<ll>(N));
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            cin >> C[i][j];
    bool ok = false;
    for (int a = 0; a < N && !ok; a++)
        for (int b = a + 1; b < N && !ok; b++)
            for (int c = b + 1; c < N; c++)
                if (C[a][b] + C[b][c] < C[a][c]) { ok = true; break; }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N^3)$
空间复杂度： $O(N^2)$

C - Puddles

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_c

题目大意

给一个 $H \times W$ 的网格，# 为黑色、. 为白色。白色格子的四连通分量（component）被称为一个区域。求完全被黑色格子包围（即不含网格最外圈任何格子）的白色连通分量的个数。最外圈指第 $1$ 行、第 $H$ 行、第 $1$ 列、第 $W$ 列。

思路

这是非常标准的连通块计数题，用 BFS / DFS 洪水填充即可：

从左上到右下扫描所有格子；
遇到一个未访问的白色格子，就从这个格子出发做一次 BFS（或 DFS），把整个连通分量全部标记为已访问；
在 BFS 过程中同时记录该连通分量是否包含过最外圈的格子；
若该分量不包含任何最外圈格子，答案加 $1$ 。

正确性在于：每个连通分量会被恰好访问一次，并且"与最外圈连通"的性质在同一个分量内是一致的（分量内任意两个格子连通，若其中一个是外圈格子，则整个分量都算与外界连通）。

实现细节： $H,W$ 最大为 $10^3$ ，网格最多 $10^6$ 个格子，递归 DFS 有爆栈风险，因此用显式队列实现 BFS。每个格子最多被访问一次，复杂度 $O(HW)$ 。

官方题解还提到可以用并查集（DSU）实现：先把所有相邻的白色格子 merge 起来，然后分别统计"所有白色分量数"与"包含外圈格子的分量数"，两者之差即为答案。这与 BFS 本质相同，但代码更短。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto& row : S) cin >> row;
    vector<vector<int>> vis(H, vector<int>(W, 0));
    int ans = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.' && !vis[i][j]) {
                queue<pair<int, int>> q;
                q.push({i, j});
                vis[i][j] = 1;
                bool onBorder = false;
                while (!q.empty()) {
                    auto [x, y] = q.front(); q.pop();
                    if (x == 0 || x == H - 1 || y == 0 || y == W - 1) onBorder = true;
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                        if (S[nx][ny] == '.' && !vis[nx][ny]) {
                            vis[nx][ny] = 1;
                            q.push({nx, ny});
                        }
                    }
                }
                if (!onBorder) ans++;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(HW)$
空间复杂度： $O(HW)$

D - Minimize Range

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_d

题目大意

给定正整数序列 $A_1, \dots, A_N$ 与正整数 $K$ 。每次操作可以任选一个下标 $i$ ，把 $A_i$ 加上 $K$ ，操作次数不限。求经过若干次操作后 $\max(A) - \min(A)$ 的最小可能值。

思路

关键观察 1：每个数除以 $K$ 的余数不变。 无论加多少次 $K$ ， $A_i \bmod K$ 是恒定不变的。所以每个数最终只能落在它自己的余数类 $\{r_i + tK \mid t \in \mathbb{Z}_{\ge 0}\}$ 中。

关键观察 2：减 $K$ 也是"免费"的。 把"给 $A_i$ 加上 $K$ "与"给除 $A_i$ 外的所有 $A_j$ 都加上 $K$ "这两种操作对比：后者得到的新序列恰好是前者得到的新序列整体加上 $K$ ，而整体平移一个常数不改变 $\max - \min$ 。由于"给所有其它数加 $K$ "可以用若干次原始操作实现，因此在允许 $\pm K$ 的模型中能达到的 $\max-\min$ 值集合，与只允许 $+K$ 的模型是完全一样的。于是我们可以认为每个数可以被替换成任意一个与 $A_i$ 同余的整数。

现在问题转化为：为每个 $i$ 在余数类 $\{r_i + tK\}_{t\in\mathbb{Z}}$ 中挑选一个值，最小化序列的极差。

关键观察 3：最优解可以看作一个宽度小于 $K$ 的"窗口"。 设最小值为 $m$ ，通过整体减 $K$ 的平移可以令 $0 \le m < K$ 。那么对每个余数 $r_i$ ，它在区间 $[m, m+K)$ 中恰好有唯一一个代表元：

v_i = \begin{cases} r_i, & r_i \ge m, \\ r_i + K, & r_i < m. \end{cases}

最小值 $m$ 必然等于某个 $r_i$ （它是某个元素选中的值，且已在 $[0,K)$ 内）。因此只需枚举 $m$ 取遍所有余数的情况。

算法（循环滑窗）：把余数排序，得 $r_0 \le r_1 \le \dots \le r_{N-1}$ 。对每个 $i$ ，考虑如下 $N$ 个数构成的集合（相当于把 $r_0, \dots, r_{N-1}$ 排成环，从 $r_i$ 起顺时针取 $N$ 个，绕回起点的那部分各自加上 $K$ ）：

\{r_i,\; r_{i+1},\; \dots,\; r_{N-1},\; r_0 + K,\; \dots,\; r_{i-1} + K\}.

这个集合的最小值是 $r_i$ ，最大值是：

\max_i = \begin{cases} r_{N-1}, & i = 0, \\ r_{i-1} + K, & i \ge 1. \end{cases}

于是答案

\text{ans} = \min_{0 \le i \le N-1} (\max_i - r_i).

这正是官方题解中"用双端队列：取出队首（最小值）、加 $K$ 后放入队尾，重复 $N$ 次，每次统计 $\max - \min$ "的做法，因为每次取出最小值加 $K$ 放回队尾，恰好让窗口顺时针滑动一步。直接排序后枚举 $i$ 也能做到同样效果。

为什么正确：任何一个可行配置平移后最小值 $m \in [0, K)$ ，且 $m$ 等于某元素的基余数 $r_i$ ；给定 $m = r_i$ 后，让每个元素取 $[m, m+K)$ 内的代表元是最优的（任何其它选择只会增大最大值而不影响最小值）。所以枚举 $i$ 覆盖了所有最优候选。

易错点： $r_{i-1} + K$ 要用 long long；当 $N=1$ 时答案为 $0$ ，上述公式自然成立。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; ll K;
    cin >> N >> K;
    vector<ll> r(N);
    for (int i = 0; i < N; i++) {
        ll a; cin >> a;
        r[i] = a % K;
    }
    sort(r.begin(), r.end());
    ll ans = LLONG_MAX;
    for (int i = 0; i < N; i++) {
        ll mx = (i == 0 ? r[N - 1] : r[i - 1] + K);
        ans = min(ans, mx - r[i]);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （排序是瓶颈）
空间复杂度： $O(N)$

E - Fibonacci String

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_e

题目大意

给定两个小写字母字符串 $X, Y$ ，定义字符串序列：

S_1 = X, \quad S_2 = Y, \quad S_i = S_{i-1} + S_{i-2}\;(i \ge 3),

其中 $+$ 表示拼接。有 $Q$ 组询问，每组给出 $L_i, R_i, C_i$ ，问字符 $C_i$ 在 $S_{10^{18}}$ 的第 $L_i$ 到第 $R_i$ 个字符中出现了多少次。

思路

关键观察 1： $S_i$ 总是 $S_{i+1}$ 的前缀。 因为 $S_{i+1} = S_i + S_{i-1}$ 。所以对任意 $K \le 10^{18}$ ， $S_K$ 都是 $S_{10^{18}}$ 的前缀。由于 $|S_i|$ 至少按 Fibonacci 数增长（ $|S_i| \ge F_i$ ，其中 $F_{88} \approx 1.1\times 10^{18}$ ），只需要取

K = \min\{k \mid |S_k| \ge 10^{18}\},

本例中 $K = 88$ 。所有询问的区间 $[L_i, R_i] \subseteq [1, 10^{18}]$ 都落在 $S_K$ 内，因此把问题从 $S_{10^{18}}$ 缩小到 $S_K$ 。

关键观察 2：区间计数化为前缀计数。 字符 $c$ 在 $[L, R]$ 内的出现次数等于"前 $R$ 个字符中的出现次数"减去"前 $L-1$ 个字符中的出现次数"。于是只需解决：求字符 $c$ 在 $S_K$ 前 $n$ 个字符中出现了多少次。

递归计数。 记 $f_c(k, n)$ 为字符 $c$ 在 $S_k$ 前 $n$ 个字符中的出现次数。利用 $S_k = S_{k-1} + S_{k-2}$ 的拼接结构，有：

f_c(k,n)= \begin{cases} c \text{ 在 } X \text{ 前 } n \text{ 个字符中出现的次数}, & k=1,\\ c \text{ 在 } Y \text{ 前 } n \text{ 个字符中出现的次数}, & k=2,\\ f_c(k-1, n), & k \ge 3,\ n \le |S_{k-1}|,\\ \mathrm{cnt}_c(S_{k-1}) + f_c(k-2,\; n - |S_{k-1}|), & k \ge 3,\ n > |S_{k-1}|. \end{cases}

其中 $\mathrm{cnt}_c(S_{k-1})$ 是字符 $c$ 在整个 $S_{k-1}$ 中的出现次数（前缀部分整段取走）。

预处理：

长度 $|S_1|, \dots, |S_K|$ ；
$X$ 、 $Y$ 的字符前缀计数数组（长度各至多 $10^4$ ，共 26 个字母）；
每个 $S_k$ 中 26 个字母各自的总出现次数 $\mathrm{cnt}_c(S_k)$ ，递推 $\mathrm{cnt}_c(S_k) = \mathrm{cnt}_c(S_{k-1}) + \mathrm{cnt}_c(S_{k-2})$ 。

查询：从 $k = K$ 开始按上面的递归式向下推进，每层要么让 $k$ 减 $1$ ，要么让 $k$ 减 $2$ 并扣掉一段前缀，深度为 $O(K) = O(\log \max R_i) \approx 88$ 。每组询问做两次前缀计数（ $R$ 与 $L-1$ ），故总复杂度 $O(Q \log \max R_i + 26(|X|+|Y|+K))$ 。

注意 $L=1$ 时 $L-1=0$ ， $n=0$ 的情形直接返回 $0$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string X, Y;
    cin >> X >> Y;
    int Q;
    cin >> Q;
    int nX = (int)X.size(), nY = (int)Y.size();
    vector<array<ll, 26>> preX(nX + 1), preY(nY + 1);
    for (int i = 0; i < nX; i++) {
        preX[i + 1] = preX[i];
        preX[i + 1][X[i] - 'a']++;
    }
    for (int i = 0; i < nY; i++) {
        preY[i + 1] = preY[i];
        preY[i + 1][Y[i] - 'a']++;
    }
    const ll LIM = 1000000000000000000LL;
    vector<ll> len = {(ll)nX, (ll)nY};
    while (len.back() < LIM) len.push_back(len[len.size() - 1] + len[len.size() - 2]);
    int K = (int)len.size();
    vector<array<ll, 26>> cnt(K);
    cnt[0] = preX[nX];
    cnt[1] = preY[nY];
    for (int i = 2; i < K; i++)
        for (int c = 0; c < 26; c++)
            cnt[i][c] = cnt[i - 1][c] + cnt[i - 2][c];
    // 字符 c 在 S_K 前 n 个字符中的出现次数
    auto count_first = [&](ll n, int c) -> ll {
        if (n <= 0) return 0;
        ll res = 0;
        int k = K - 1;              // 0-indexed: len[k] = |S_{k+1}|, cnt[k][c] 对应 S_{k+1}
        while (k >= 2) {
            if (n <= len[k - 1]) {  // 落在前半段 S_{k}
                k--;
            } else {                // 前半段整段计入，进入后半段 S_{k-1}
                res += cnt[k - 1][c];
                n -= len[k - 1];
                k -= 2;
            }
        }
        if (k == 1) res += preY[(int)n][c];  // S_2 = Y
        else res += preX[(int)n][c];         // S_1 = X
        return res;
    };
    while (Q--) {
        ll L, R; char C;
        cin >> L >> R >> C;
        int c = C - 'a';
        cout << count_first(R, c) - count_first(L - 1, c) << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(26(|X| + |Y| + K) + QK)$ ，其中 $K = O(\log \max R_i) \approx 88$
空间复杂度： $O(26 \cdot (|X| + |Y| + K))$

F - Strongly Connected 2

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_f

题目大意

有一个 $N$ 个顶点的有向图，顶点编号 $1..N$ 。共有 $N-1+M$ 条边：

对 $1 \le i \le M$ ，边 $i$ 是 $X_i \to Y_i$ ，且保证 $X_i < Y_i$ ；
对 $1 \le i \le N-1$ ，边 $M+i$ 是 $i+1 \to i$ 。

从边 $1..M$ 中任意选择一些边（保留），其余删去，问有多少种选择方式（共 $2^M$ 种）使得剩下的图是强连通的。答案对 $998244353$ 取模。

思路

第一步：化简强连通条件。 注意 $N-1$ 条链边 $i+1 \to i$ 使得从任意顶点都能沿编号递减的方向走到任何编号更小的顶点，也就是任意 $u > v$ 都有路径 $u \to u-1 \to \dots \to v$ 。于是整个图强连通等价于"从 $1$ 能到达 $N$ "：

若从 $1$ 能到达 $N$ ，则对任意 $u < v$ ，有路径 $u \to (u-1) \to \dots \to 1 \to (\text{保留的边}) \to N \to (N-1) \to \dots \to v$ ，即任意两点互相可达；
反之强连通当然意味着 $1$ 能到达 $N$ 。

而保留的边全部满足 $X < Y$ （只能"向前"走），所以问题变成：计数保留边的子集，使 $1$ 能沿保留边到达 $N$ 。

第二步：可达性用一个数刻画。 从 $1$ 出发，每到达某个顶点 $m$ 就能沿链边回退到 $1, \dots, m$ 中任意一个。因此"当前最大可达顶点"是一个数 $m$ ，可达集恰为 $\{1, 2, \dots, m\}$ 。此时任何一条保留边 $(X, Y)$ 只要满足 $X \le m$ 就立即可用，把最大可达顶点点更新为 $\max(m, Y)$ 。

第三步：DP。 把所有边按 $X$ 升序排序，依次"加入"（考虑选或不选）。设 $\mathrm{dp}[i][r]$ 为考虑前 $i$ 条边后，从 $1$ 出发最大可达顶点恰为 $r$ 的选择方案数。对边 $(X_i, Y_i)$ ：

\mathrm{dp}[i][r]= \begin{cases} 2\,\mathrm{dp}[i-1][r], & r < X_i, \\ \mathrm{dp}[i-1][r], & X_i \le r < Y_i, \\ \mathrm{dp}[i-1][Y_i] + \sum_{r'=X_i}^{Y_i}\mathrm{dp}[i-1][r'], & r = Y_i,\\ 2\,\mathrm{dp}[i-1][r], & r > Y_i. \end{cases}

逐条解释：

$r < X_i$ ：这条边的起点 $X_i$ 还不可达，选或不选都改变不了当前可达范围，方案数翻倍（边先"存着"，将来可达范围扩大后自然可用）；
$X_i \le r < Y_i$ ：选它会把可达范围撑大到 $Y_i > r$ ，所以只有"不选"能保持 $r$ ；
$r = Y_i$ ：要么之前就可达 $Y_i$ 且本次不选（ $\mathrm{dp}[i-1][Y_i]$ ），要么之前可达范围为 $[X_i, Y_i]$ 中的某个 $r'$ 且本次选上（ $\sum_{r'=X_i}^{Y_i}\mathrm{dp}[i-1][r']$ ， $r'=Y_i$ 时选上也不变）——注意这两类互不重叠，故直接相加；
$r > Y_i$ ：选或不选都不会改变可达范围，翻倍。

初始 $\mathrm{dp}[1]=1$ （空子集，最大可达顶点为 $1$ ）。答案即处理完全部 $M$ 条边后的 $\mathrm{dp}[N]$ （最大可达顶点为 $N$ 当且仅当 $1$ 能到达 $N$ ）。

第四步：优化。 直接按上述递推做是 $O(NM)$ 的。观察需要支持的操作恰好有三种：区间求和（ $[X_i, Y_i]$ ）、区间乘 $2$ （ $r > Y_i$ ）、单点加（ $r = Y_i$ 处加上求和结果）。用懒标记线段树（支持区间乘、区间和、单点加）即可做到 $O((N+M)\log N)$ 。另外， $r < X_i$ 的部分永远不会对 $\mathrm{dp}[N]$ 有贡献（之后所有边的 $X' \ge X_i$ ，其求和区间与乘法区间都不会碰 $r < X_i$ ），因此这一段的翻倍操作可以省略。

注意输入的边可能存在重边，按题意每条边都是独立的、可分别选择，DP 会自然地把它们当作不同边处理。

参考代码

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

struct SegTree {
    int n;
    vector<ll> sum, lazy;
    SegTree(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        sum.assign(2 * n, 0);
        lazy.assign(2 * n, 1);
    }
    void apply(int p, ll v) {
        sum[p] = sum[p] * v % MOD;
        lazy[p] = lazy[p] * v % MOD;
    }
    void push(int p) {
        if (lazy[p] != 1) {
            apply(p * 2, lazy[p]);
            apply(p * 2 + 1, lazy[p]);
            lazy[p] = 1;
        }
    }
    void rangeMul(int l, int r, ll v) { if (l > r) return; rangeMul(l, r, v, 1, 0, n - 1); }
    void rangeMul(int l, int r, ll v, int p, int cl, int cr) {
        if (r < cl || cr < l) return;
        if (l <= cl && cr <= r) { apply(p, v); return; }
        push(p);
        int mid = (cl + cr) / 2;
        rangeMul(l, r, v, p * 2, cl, mid);
        rangeMul(l, r, v, p * 2 + 1, mid + 1, cr);
        sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % MOD;
    }
    void pointAdd(int idx, ll v) { pointAdd(idx, v, 1, 0, n - 1); }
    void pointAdd(int idx, ll v, int p, int cl, int cr) {
        if (cl == cr) { sum[p] = (sum[p] + v) % MOD; return; }
        push(p);
        int mid = (cl + cr) / 2;
        if (idx <= mid) pointAdd(idx, v, p * 2, cl, mid);
        else pointAdd(idx, v, p * 2 + 1, mid + 1, cr);
        sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % MOD;
    }
    ll rangeSum(int l, int r) { if (l > r) return 0; return rangeSum(l, r, 1, 0, n - 1); }
    ll rangeSum(int l, int r, int p, int cl, int cr) {
        if (r < cl || cr < l) return 0;
        if (l <= cl && cr <= r) return sum[p];
        push(p);
        int mid = (cl + cr) / 2;
        return (rangeSum(l, r, p * 2, cl, mid) + rangeSum(l, r, p * 2 + 1, mid + 1, cr)) % MOD;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; i++) cin >> edges[i].first >> edges[i].second;
    sort(edges.begin(), edges.end());
    SegTree st(N);          // 位置 pos 对应顶点 pos+1
    st.pointAdd(0, 1);      // dp[顶点1] = 1
    for (auto [X, Y] : edges) {
        ll s = st.rangeSum(X - 1, Y - 1);   // r' 从 X 到 Y 的和
        st.rangeMul(Y, N - 1, 2);           // r > Y 的部分乘 2
        st.pointAdd(Y - 1, s);              // dp[Y] += s
    }
    cout << st.rangeSum(N - 1, N - 1) << '\n';
    return 0;
}

复杂度分析

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

G - Random Subtraction

题目链接：https://atcoder.jp/contests/abc450/tasks/abc450_g

题目大意

给定 $N$ 个非负整数 $A_1, \dots, A_N$ 。重复如下操作直到只剩一个数：均匀随机地选两个不同下标 $i, j$ ，把 $A_i, A_j$ 从序列中移除，并在末尾加入 $A_i - A_j$ 。设最后剩下的数为 $x$ ，求 $E[x^2]$ 对 $998244353$ 取模。

思路

第一步：把 $x$ 表示成系数的线性组合。 每次操作把两个数合并成它们的差，等价于把"两个元素各自贡献的符号"合并：若新元素最终带符号 $s \in \{+1,-1\}$ ，则 $A_i$ 带符号 $s$ 、 $A_j$ 带符号 $-s$ 。经过 $N-1$ 次合并，最终

x = \sum_{i=1}^{N} c_i A_i, \qquad c_i \in \{+1, -1\}.

于是

x^2 = \sum_{i=1}^{N} A_i^2 + 2 \sum_{1 \le i < j \le N} c_i c_j A_i A_j.

其中 $\sum A_i^2$ 是常量，与随机过程无关。由对称性，任意不同的一对 $(i,j)$ 其 $c_i c_j$ 的期望都相同，记为 $e_N$ ，则

E[x^2] = \sum_{i=1}^{N} A_i^2 + 2 e_N \sum_{i<j} A_i A_j = \sum_{i=1}^{N} A_i^2 + e_N \left[\left(\sum_{i=1}^{N} A_i\right)^2 - \sum_{i=1}^{N} A_i^2\right],

最后一个等号用了恒等式 $2\sum_{i<j} A_i A_j = (\sum_i A_i)^2 - \sum_i A_i^2$ 。

第二步：求 $e_N = E[c_i c_j]$ 。 记

C_N := E\left[\sum_{1 \le i < j \le N} c_i c_j\right] = \binom{N}{2} e_N.

利用归纳：不妨设第一步合并的是 $A_1$ 与 $A_2$ （下标对任意重排，期望相同）。设合并出的新元素 $A_1 - A_2$ 最终带的符号为 $s$ ，那么 $c_1 = s$ 、 $c_2 = -s$ ，于是：

$c_1 c_2 = -1$ 恒成立；
对 $i \ge 3$ ， $c_1 c_i + c_2 c_i = s c_i - s c_i = 0$ 恒成立；
对 $3 \le i < j$ ， $(c_i, c_j)$ 的联合分布与"以 $N-1$ 个元素开始的独立新过程"中任意两元素的符号联合分布完全相同（因为去掉 $A_1, A_2$ 、换入 $A_1-A_2$ 后，剩余步骤就是同样的随机过程，而符号分布只取决于元素个数、与取值无关），因此

E[c_i c_j] = \frac{C_{N-1}}{\binom{N-1}{2}}.

由此得到递推：

C_N = -1 + \binom{N-2}{2}\cdot \frac{C_{N-1}}{\binom{N-1}{2}} = -1 + \frac{(N-2)(N-3)/2}{(N-1)(N-2)/2}\, C_{N-1} = -1 + \frac{N-3}{N-1}\, C_{N-1},

初值 $C_1 = 0$ （没有元素对）。逐个计算 $C_2, \dots, C_N$ ，复杂度 $O(N)$ 。最后

e_N = \frac{C_N}{\binom{N}{2}} = \frac{2\,C_N}{N(N-1)},

代入第一步的公式即可。所有除法均用模意义下的逆元处理；当 $N=1$ 时答案为 $A_1^2$ ，直接特判。

参考代码

#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;
    ll sum = 0, sumsq = 0;
    for (int i = 0; i < N; i++) {
        ll a; cin >> a;
        a %= MOD;
        sum = (sum + a) % MOD;
        sumsq = (sumsq + a * a) % MOD;
    }
    if (N == 1) {
        cout << sumsq << '\n';
        return 0;
    }
    ll C = 0;                       // C_1 = 0
    for (int n = 2; n <= N; n++) {
        ll coef = (n - 3 + MOD) % MOD * modpow(n - 1, MOD - 2) % MOD;
        C = (MOD - 1 + coef * C) % MOD;   // C_n = -1 + (n-3)/(n-1) * C_{n-1}
    }
    ll e = C * 2 % MOD * modpow((ll)N * (N - 1) % MOD, MOD - 2) % MOD;
    ll ans = (sumsq + e * ((sum * sum % MOD - sumsq + MOD) % MOD)) % MOD;
    cout << ans << '\n';
    return 0;
}

复杂度分析

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