AtCoder Beginner Contest 470 题解

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

AtCoder Beginner Contest 470 题解

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

比赛概览

本场 ABC470 整体难度分布合理：A、B 是纯入门模拟；C 题考查"维护全局 XOR 的差分式更新"并附带一个精巧的摊还分析；D 题是排列与逆排列的双数组经典技巧；E 题是需要先做期望分解、再做 $O(LN^2)$ 期望 DP 的记忆配对游戏；F 题将问题归结为"连通分量上的置换 + 奇偶性 + 多重集排列计数"，很有区分度；G 题是"所有子数组 mex 之和"，用 $\mathrm{mex}=\sum_k \mathrm{haveall}_k$ 的恒等式转化为区间覆盖计数，再借助单调性用分段常数区间维护，是本场最难也最值得掌握的题目。建议重点吃透 C 的摊还思想、D 的"逆排列随取随用"技巧，以及 F、G 两个较综合的题目。

A - Fizz

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_a

题目大意

给定正整数 $N$ （ $1\le N\le 100$ ），输出 $N$ 行：第 $i$ 行（ $1\le i\le N$ ）若 $i$ 是 $3$ 的倍数则输出 Fizz，否则输出 $i$ 本身。

思路

直接按题意模拟即可：用一条 for 循环遍历 $i=1,2,\ldots,N$ ，每次判断 i % 3 == 0：

若整除，输出字符串 Fizz；
否则输出整数 $i$ 。

这是最简单的入门题，唯一需要注意的易错点是：输出的是"当且仅当 $i$ 是 $3$ 的倍数时才输出 Fizz"，其余情况原样输出数字，不要自己多加"若同时是 5 的倍数"之类不存在的条件。

正确性：循环恰好遍历全部 $N$ 个 $i$ ，每个 $i$ 按条件输出，与题意完全一致。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        if (i % 3 == 0) cout << "Fizz\n";
        else cout << i << "\n";
    }
    return 0;
}

官方题解给出的 Python 实现：

n = int(input())
for k in range(1, n + 1):
    if k % 3 == 0:
        print("Fizz")
    else:
        print(k)

复杂度分析

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

B - Monocolor

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_b

题目大意

有 $N$ 个球，第 $i$ 个球的颜色为 $C_i$ （ $1\le C_i\le N$ ， $1\le N\le 100$ ）。一次操作可以任选一个球并把它改成 $N$ 种颜色中的任意一种。求把所有球改成同一种颜色所需的最少操作次数。

思路

设最终所有球都变成颜色 $c$ 。那么初始颜色不等于 $c$ 的球必须全部被改掉，所以操作数至少为 $N-\mathrm{cnt}[c]$ ，其中 $\mathrm{cnt}[c]$ 表示初始颜色为 $c$ 的球的数量。

反过来，如果选定了一个目标颜色 $c$ ，把其余 $N-\mathrm{cnt}[c]$ 个球全部改成 $c$ 即可达到这个操作数。因此最优策略就是：

选择初始出现次数最多的颜色作为目标颜色，答案即为
$N-\max_c \mathrm{cnt}[c].$

为什么正确：下界 $N-\mathrm{cnt}[c]$ 对任意 $c$ 都成立，而上界 $N-\mathrm{cnt}[c_{\max}]$ 是可构造的，两者相撞即得答案。

实现上开一个大小为 $N+1$ 的计数数组扫一遍统计频次即可。 $N\le 100$ ，用哈希表也完全可以。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> cnt(N + 1, 0);
    for (int i = 0; i < N; i++) {
        int c;
        cin >> c;
        cnt[c]++;
    }
    int mx = 0;
    for (int c = 1; c <= N; c++) mx = max(mx, cnt[c]);
    cout << N - mx << "\n";
    return 0;
}

官方题解给出的 Python 实现：

n = int(input())
c = list(map(int, input().split()))
cnt = [0] * n
for v in c:
    cnt[v - 1] += 1
print(n - max(cnt))

复杂度分析

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

C - Inc, Dec, Xor

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_c

题目大意

有一个长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$ ，初始全为 $0$ 。按顺序处理 $Q$ 个操作，每次操作后输出 $A_1\oplus A_2\oplus\cdots\oplus A_N$ ：

1 x：给 $A_x$ 加 $1$ ；
2：对每个满足 $A_i\ge 1$ 的 $i$ ，把 $A_i$ 减 $1$ 。

约束： $1\le N,Q\le 5\times 10^5$ 。

思路

设 $f(A)=A_1\oplus\cdots\oplus A_N$ 为当前整个数组的 XOR。朴素做法是每次操作都重新计算 $f$ ，但 $Q$ 次操作每次 $O(N)$ 会超时。

关键观察 1：XOR 的差分式更新。 如果某个元素从 $v$ 变成了 $v'$ ，其余元素不变，那么新 XOR 为

f' = f\oplus v\oplus v' .

因为旧贡献是 $v$ 、新贡献是 $v'$ ，而 $f\oplus v\oplus v' = (f\oplus v)\oplus v'$ 恰好把 $v$ 换成 $v'$ 。

类型 1： $A_x$ 从 $v$ 变为 $v+1$ ，于是 ans ^= v ^ (v + 1); a[x]++;。
类型 2：对每个正元素 $v$ ，它变为 $v-1$ ，于是 ans ^= v ^ (v - 1); a[v]--;。

关键观察 2：如何快速枚举"所有正元素"。 类型 2 若去扫描全部 $N$ 个位置会 TLE。改为维护一个"当前值 $\ge 1$ 的下标集合"（用 std::vector 即可）：

类型 1 把一个元素加 1，如果它原来为 0，就把该下标加入集合；
类型 2 遍历整个集合，逐个减 1，并把减后变为 0 的下标从集合中移除。

为什么总复杂度是 $O(N+Q)$ （摊还）？ 类型 2 每遍历到一个正元素，就意味着该元素被减 1，即"总和"减少 1。而整个过程中"总和"总共被类型 1 增加了至多 $Q$ 次（每次加 1）。所以所有类型 2 的遍历总量至多等于类型 1 的总次数 $Q$ 。因此全程的总工作量是 $O(N+Q)$ 。

实现细节：类型 2 移除归零下标时采用"原地压缩"写法（用一个写指针 w 边遍历边保留非零下标），避免每次重建整个 vector 带来的额外开销；每个下标至多被加入一次、删除一次，这正是摊还分析成立的前提。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N, 0);
    vector<int> idxs;   // 当前值 >= 1 的下标
    int ans = 0;        // 整个数组的 XOR
    for (int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            --x;
            if (a[x] == 0) idxs.push_back(x);
            ans ^= a[x] ^ (a[x] + 1);
            a[x]++;
        } else {
            int w = 0;
            for (int v : idxs) {
                ans ^= a[v] ^ (a[v] - 1);
                a[v]--;
                if (a[v] != 0) idxs[w++] = v;   // 保留仍为正的元素
            }
            idxs.resize(w);
        }
        cout << ans << "\n";
    }
    return 0;
}

官方题解给出的 Python 实现：

input = __import__("sys").stdin.readline
n, q = map(int, input().split())
idxs = []
a = [0] * n
ans = 0
for _ in range(q):
    data = list(map(int, input().split()))
    if data[0] == 1:
        x = data[1] - 1
        if a[x] == 0:
            idxs.append(x)
        ans ^= a[x] ^ (a[x] + 1)
        a[x] += 1
    else:
        for v in idxs:
            ans ^= a[v] ^ (a[v] - 1)
            a[v] -= 1
        idxs = [v for v in idxs if a[v] != 0]
    print(ans)

复杂度分析

时间复杂度： $O(N+Q)$ （摊还）
空间复杂度： $O(N)$

D - Inverse and Swap

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_d

题目大意

给定一个 $(1,\ldots,N)$ 的排列 $P=(P_1,\ldots,P_N)$ 。按顺序处理 $Q$ 个操作：

1 x y：交换 $P_x$ 与 $P_y$ 的值；
2：把 $P$ 替换成满足 $P_{P'_i}=i$ 的唯一排列 $P'$ （即 $P'$ 是 $P$ 的逆排列）。

输出处理完所有操作后的 $P_1,\ldots,P_N$ 。约束： $2\le N,Q\le 5\times 10^5$ 。

思路

把排列 $P$ 看成一个双射映射

\begin{pmatrix}1&2&\cdots&N\\ P_1&P_2&\cdots&P_N\end{pmatrix}.

那么类型 2 就是把 $P$ 换成它的逆映射 $P^{-1}$ （写作 $\begin{pmatrix}P_1&P_2&\cdots&P_N\\ 1&2&\cdots&N\end{pmatrix}$ ）。若每次类型 2 都 $O(N)$ 求逆，最坏 $O(NQ)$ 会 TLE。

关键观察 1：同时维护 $P$ 与 $P^{-1}$ 。 类型 1 只影响两个元素：

交换 $P_x$ 与 $P_y$ 后，值 $P_x$ 所在的位置从 $x$ 变成了 $y$ ，值 $P_y$ 所在的位置从 $y$ 变成了 $x$ 。反映到逆排列上，就是交换 $P^{-1}_{P_x}$ 与 $P^{-1}_{P_y}$ 。

所以类型 1 可以 $O(1)$ 同时更新两个数组。

关键观察 2：类型 2 只需翻转一个标志。 因为 $(P^{-1})^{-1}=P$ ，即" $P$ 和 $P^{-1}$ 互为对方"，所以类型 2 只需把"当前哪一个是 $P$ "的标志取反，根本不需要移动数据。

实现：开两个数组 pq[0]、pq[1]，初始令 pq[0] 为 $P$ （转成 0-indexed），pq[1] 为 $P^{-1}$ （满足 pq[1][P_i] = i），标志位 pi 表示当前 $P$ 存在哪个数组里。注意类型 1 中，px = pq[pi][x]、py = pq[pi][y] 必须先用旧值取出再交换。

边界情况：下标都先减 1 变成 0-indexed；类型 1 保证 $x<y$ ，但不影响处理。 $Q$ 次操作后输出 pq[pi] 并加 1 还原。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> pq[2];
    pq[0].resize(N);
    for (int i = 0; i < N; i++) {
        cin >> pq[0][i];
        pq[0][i]--;
    }
    pq[1].assign(N, 0);
    for (int i = 0; i < N; i++) {
        pq[1][pq[0][i]] = i;
    }
    int pi = 0;  // 当前 P 存放在 pq[pi] 中
    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            --x; --y;
            int px = pq[pi][x], py = pq[pi][y];
            swap(pq[pi][x], pq[pi][y]);          // 交换 P 中的两个值
            swap(pq[pi ^ 1][px], pq[pi ^ 1][py]); // 同步更新逆排列
        } else {
            pi ^= 1;                              // 取逆：翻转标志
        }
    }
    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << pq[pi][i] + 1;
    }
    cout << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(N+Q)$ （预处理 $O(N)$ ，每个查询 $O(1)$ ，输出 $O(N)$ ）
空间复杂度： $O(N)$

E - Concentration

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_e

题目大意

有 $2N$ 张牌，每张牌正面写着一个数字，其中数字 $A_i$ 恰好出现两次（ $A_1<\cdots<A_N$ ）。牌被随机打乱并正面朝下放置。生命值为 $L$ 、分数为 $0$ ，重复以下流程直到生命为 $0$ 或桌上无牌：

翻开一张面朝下的牌，得知其数字 $X$ ；
再翻开一张面朝下的牌，得知其数字 $Y$ ；
若 $X=Y$ ，把这两张牌移出桌面，分数增加 $X$ ；否则盖回两张牌，生命减 $1$ 。

Takahashi 知道规则与所有 $A_i$ ，并会以最大化最终期望分数为目标最优地行动。求期望分数。约束： $1\le N,L\le 200$ ， $1\le A_i\le 10^5$ 。

思路

第一步：把"分数"分解成"对数 $\times$ 平均数字"。

先看最优策略是否依赖牌面上的具体数字。当某张牌被翻开得到数字 $X$ 时，Takahashi 的后续选择只有"翻哪张未知牌"；而所有未知牌对他来说完全不可区分。当他拿到一对已知的配对时，立刻取走这对总是最优的（配对不消耗生命）。也就是说：存在一个不依赖牌面数字的最优策略，它只取决于"当前已知了几张互不相同的牌、还剩几对完全未知的牌、生命值是多少"这类信息状态。

于是所有配对在策略层面完全对称：每对牌最终被取到的概率都相等。设 $X$ 为最优策略下期望配对数，则期望分数

\mathbb{E}[\text{score}] = X\cdot \frac{A_1+A_2+\cdots+A_N}{N}.

这是因为每对被取到的概率都是 $X/N$ ，而被取到的牌对贡献它的数字 $A_i$ 。因此问题转化为：求能最大化期望配对数的策略的期望配对数 $X$ 。

第二步：定义状态与转移。

用 $f(L,C_0,C_1)$ 表示"当前生命为 $L$ ，桌上还剩 $C_0$ 对完全未知的牌（ $2C_0$ 张），以及 $C_1$ 张已翻开且数字两两不同的牌（它们的配对仍在桌上，故对应 $C_1$ 对"半已知"的牌）"时，从今往后能获得的期望配对数。桌上牌总数为 $2(C_0+C_1)$ ，其中面朝下的牌数为

T = 2C_0 + C_1 .

由于所有未知牌不可区分，最优策略为：第一张永远翻未知牌；若翻出的数字与某张已知牌相同，则第二张直接取那张已知牌完成配对；否则第二张也翻未知牌（翻已知牌不会带来任何新信息，被支配）。

考虑一回合的四种结果：

第一张是某张已知牌的配对：概率 $\dfrac{C_1}{T}$ 。直接配对成功，得 $1$ 对，转入 $f(L,C_0,C_1-1)$ 。
第一张是新数字，第二张正好是它的配对：概率 $\dfrac{2C_0}{T}\cdot\dfrac{1}{T-1}$ 。得 $1$ 对，转入 $f(L,C_0-1,C_1)$ 。
第一张是新数字，第二张是某张已知牌的配对：概率 $\dfrac{2C_0}{T}\cdot\dfrac{C_1}{T-1}$ 。本回合配对失败、生命减 1，但此时我们掌握了一对完整的配对（第二张和它早先被翻开的搭档），只要生命还剩（ $L\ge 2$ ），下一回合必取走这对。贡献为 $1+f(L-1,C_0-1,C_1)$ （第一张新牌使其配对变为半已知，故 $C_0$ 减 1 而 $C_1$ 不变）；若 $L=1$ ，本回合后生命归零，这对再也取不到，贡献为 $0$ 。
第一、二张都是不同的新数字：概率 $\dfrac{2C_0}{T}\cdot\dfrac{2C_0-2}{T-1}$ 。两对牌都变成"半已知"，转入 $f(L-1,C_0-2,C_1+2)$ 。

（校验概率： $1+C_1+(2C_0-2)=2C_0+C_1-1=T-1$ ，恰为第二张牌的所有可能。）

于是得到递推式

\begin{aligned} f(L,C_0,C_1) &=\frac{C_1}{T}\Big(1+f(L,C_0,C_1-1)\Big)\\ &\quad+\frac{2C_0}{T}\frac{1}{T-1}\Big(1+f(L,C_0-1,C_1)\Big)\\ &\quad+\frac{2C_0}{T}\frac{C_1}{T-1}\Big[L\ge 2?\;1+f(L-1,C_0-1,C_1):0\Big]\\ &\quad+\frac{2C_0}{T}\frac{2C_0-2}{T-1}\,f(L-1,C_0-2,C_1+2). \end{aligned}

边界条件：

$f(0,\cdot,\cdot)=0$ （生命耗尽，游戏结束）；
$f(L,0,C_1)=C_1$ （全部配对都已翻开一半，逐个取走即可，不消耗生命）。

为什么递推能顺利计算：所有转移都把量 $2C_0+C_1$ 严格减小，因此按 $2C_0+C_1$ 从小到大（再按 $L$ 从小到大）迭代即可，状态数 $O(LN^2)$ ，每个状态常数个转移。注意实现时若用记忆化递归，常数大容易 TLE，建议用迭代填表。

最终答案 $=f(L,N,0)\cdot\dfrac{\sum A_i}{N}$ 。例如样例 1： $f(2,3,0)=\dfrac{29}{15}$ ， $\dfrac{\sum A}{N}=2$ ，答案为 $\dfrac{58}{15}\approx 3.8666666667$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, L;
    cin >> N >> L;
    vector<long long> A(N);
    long long sumA = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sumA += A[i];
    }

    // f[l][c0][c1]：生命 l，c0 对完全未知，c1 张已翻开（数字两两不同）
    vector<vector<vector<double>>> f(L + 1,
        vector<vector<double>>(N + 1, vector<double>(N + 1, 0.0)));
    for (int s = 0; s <= 2 * N; s++) {   // s = 2*c0 + c1 每次转移严格减小
        for (int c0 = 0; c0 <= N; c0++) {
            int c1 = s - 2 * c0;
            if (c1 < 0 || c1 > N) continue;
            for (int l = 0; l <= L; l++) {
                if (l == 0) { f[l][c0][c1] = 0.0; continue; }
                if (c0 == 0) { f[l][c0][c1] = (double)c1; continue; }
                double T = 2.0 * c0 + c1;   // 面朝下的牌数
                double res = 0.0;
                if (c1 > 0) {
                    // 第一张匹配某张已翻开牌
                    res += (double)c1 / T * (1.0 + f[l][c0][c1 - 1]);
                }
                double pb = 2.0 * c0 / T;   // 第一张是新数字
                // 第二张正好是它的配对
                res += pb / (T - 1.0) * (1.0 + f[l][c0 - 1][c1]);
                // 第二张是某张已翻开牌的配对（下回合取走这对）
                if (l >= 2 && c1 > 0) {
                    res += pb * (double)c1 / (T - 1.0) * (1.0 + f[l - 1][c0 - 1][c1]);
                }
                // 第二张也是新数字
                if (2 * c0 - 2 > 0) {
                    res += pb * (double)(2 * c0 - 2) / (T - 1.0) * f[l - 1][c0 - 2][c1 + 2];
                }
                f[l][c0][c1] = res;
            }
        }
    }

    double X = f[L][N][0];                        // 期望配对数
    double ans = X * (double)sumA / N;
    cout << fixed << setprecision(10) << ans << "\n";
    return 0;
}

复杂度分析

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

F - Googol Swaps

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_f

题目大意

给定长度为 $N$ 的小写字母字符串 $S$ ，以及 $M$ 对下标 $(A_i,B_i)$ （互不相同）。每次操作选一个 $i$ ，交换 $S$ 的第 $A_i$ 与第 $B_i$ 个字符。求恰好执行 $10^{100}$ 次操作后， $S$ 可能变成的不同字符串个数，对 $998244353$ 取模。约束： $2\le N,M\le 2\times 10^5$ 。

思路

第一步：转化为图上的置换。 建一张 $N$ 个顶点的无向图，顶点代表字符位置，每条边 $(A_i,B_i)$ 代表一种可选操作。于是每次操作就是交换一条边两端顶点的字符。

用排列 $p=(p_1,\ldots,p_N)$ 表示"原本在顶点 $i$ 的字符最终移到了顶点 $p_i$ "。每交换一次，就相当于乘上一个对换（transposition）。因此经过 $10^{100}$ 次操作后得到的排列 $p$ 必然满足两条性质：

条件 A（奇偶性）：每个对换都是奇排列，故操作数为偶数时 $p$ 必为偶排列。 $10^{100}$ 是偶数，所以 $p$ 必须是偶排列。
条件 B（连通分量不变）：字符只能在连通分量内部移动，故每个连通分量的顶点集合在 $p$ 下保持不变。

第二步：两条性质也是充分的。 对任意满足条件 B 的排列 $p$ ，因为连通分量的"边对换生成的群"是整个对称群（沿生成树可用两次相邻交换合成任意对换）， $p$ 在 $N^2$ 次操作内可达（官方题解给出按生成树叶子逐一归位的归纳证明： $t+(t-1)^2\le t^2$ 递推）。若 $p$ 还是偶排列，则达到它的操作数必为偶数；之后反复执行同一条操作两次（恒等变换）即可把操作数补齐到恰好 $10^{100}$ 。综上：

$S$ 最终可能变成的字符串，恰好对应所有满足条件 A、B 的排列 $p$ 。

第三步：按连通分量计数。 每个分量独立计数后相乘。设一个分量大小为 $s$ ，其中字符 $c$ 出现 $c_c$ 次，则该分量内部"字符重排"的种类数为多重集排列数

\frac{s!}{c_1!\,c_2!\cdots c_\sigma!}.

但还要受"全局偶排列"约束，分两种情况：

分量内存在重复字符：此时对分量内任意一种排列，既存在偶排列实现它、也存在奇排列实现它（把两个相同字符的位置对调，排列奇偶性改变而字符排列不变）。于是该分量的奇偶性"自由"，可以任意调节以配合其它分量。
分量内字符两两不同：排列与字符排列一一对应，其中恰有一半为偶排列。

全局约束是总排列为偶排列。若至少一个分量内有重复字符，用它即可把总奇偶性调成偶数，因此所有全局字符排列都可达，不除 2；若所有分量内字符都两两不同，则各分量奇偶性均被锁定，全局恰有一半排列为偶，答案需要除以 2。

实现：并查集（DSU）找出连通分量，对每个分量统计 26 种字母频次，计算多重集排列数之积（模 $998244353$ ），最后若不存在含重复字母的分量则乘以 $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, M;
    cin >> N >> M;
    string S;
    cin >> S;

    vector<int> parent(N);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    auto unite = [&](int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[rb] = ra;
    };
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        unite(a - 1, b - 1);
    }

    vector<ll> fact(N + 1), invfact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[N] = modpow(fact[N], MOD - 2);
    for (int i = N; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

    unordered_map<int, array<int, 26>> cnt;
    for (int i = 0; i < N; i++) {
        int r = find(i);
        cnt[r][S[i] - 'a']++;
    }

    ll ans = 1;
    bool anyRepeat = false;
    for (auto &kv : cnt) {
        int sz = 0;
        bool rep = false;
        for (int c = 0; c < 26; c++) {
            sz += kv.second[c];
            if (kv.second[c] >= 2) rep = true;
        }
        ll mult = fact[sz];
        for (int c = 0; c < 26; c++) mult = mult * invfact[kv.second[c]] % MOD;
        ans = ans * mult % MOD;
        if (rep) anyRepeat = true;
    }
    // 若所有分量内字符都两两不同，则恰有一半排列为偶排列
    if (!anyRepeat) ans = ans * modpow(2, MOD - 2) % MOD;

    cout << ans << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O((N+M)\,\alpha(N))$ （ $\alpha$ 为反阿克曼函数，并查集近似线性）
空间复杂度： $O(N)$

G - ΣШX

题目链接：https://atcoder.jp/contests/abc470/tasks/abc470_g

题目大意

给定长度 $N$ 的非负整数序列 $A=(A_1,\ldots,A_N)$ （ $1\le N\le 3\times 10^5$ ， $0\le A_i\le N$ ）。求所有子数组 $A_l,\ldots,A_r$ （ $1\le l\le r\le N$ ）的 $\mathrm{mex}$ 之和，其中 $\mathrm{mex}$ 是"子数组中未出现的最小非负整数"。

思路

第一步：mex 的计数恒等式。 对任意子数组 $[l,r]$ ，定义 $\mathrm{haveall}_k([l,r])$ 为 $0,1,\ldots,k$ 是否全部出现在 $[l,r]$ 中（是为 1，否为 0）。若 $\mathrm{mex}=m$ ，则 $0,\ldots,m-1$ 全在而 $m$ 不在，于是

\sum_{k=0}^{N-1}\mathrm{haveall}_k([l,r]) = m = \mathrm{mex}([l,r]).

因为每个 $k<m$ 恰好贡献 1， $k\ge m$ 贡献 0。由于 $\mathrm{mex}\le N$ （子数组长度 $\le N$ ，值域只有 $0,\ldots,N$ 共 $N+1$ 个值，必有一个在 $0..N$ 中缺失），求和只需到 $N-1$ 。

交换求和顺序，设 $S_k=\{[l,r]\mid \mathrm{haveall}_k([l,r])=1\}$ 为"包含 $0,\ldots,k$ 全部值"的子数组集合，则答案

\sum_{[l,r]}\mathrm{mex}([l,r]) = \sum_{k=0}^{N-1}|S_k| .

问题变成对每个 $k$ 统计 $|S_k|$ 。

第二步：固定 $k$ 的计数。 对每个左端点 $l$ ，定义

\mathrm{next}_m[l]=\min\{r\ge l\mid A_r=m\}\cup\{N+1\}

即从 $l$ 起（含 $l$ ）第一次出现 $m$ 的位置，不存在则为 $N+1$ 。再令

\mathrm{maxnext}_k[l]=\max_{0\le m\le k}\mathrm{next}_m[l].

则 $[l,r]\in S_k$ 当且仅当 $\mathrm{maxnext}_k[l]\le r\le N$ ，个数为 $N+1-\mathrm{maxnext}_k[l]$ 。故

|S_k|=\sum_{l=1}^{N}\bigl(N+1-\mathrm{maxnext}_k[l]\bigr).

第三步：从 $k-1$ 递推到 $k$ 。 显然

\mathrm{maxnext}_k[l]=\max\bigl(\mathrm{maxnext}_{k-1}[l],\ \mathrm{next}_k[l]\bigr).

设值为 $k$ 的位置为 $x_1<\cdots<x_c$ ，并设哨兵 $x_0=0,\ x_{c+1}=N+1$ 。则对 $i=1,\ldots,c+1$ ，在区间 $[x_{i-1}+1,\ x_i]$ 上 $\mathrm{next}_k[l]=x_i$ 。也就是说：对每个 $i$ ，在区间 $[x_{i-1}+1,\ x_i]$ 上做一次"chmax 到 $x_i$ "。

第四步：用单调性加速 chmax。 每个 $\mathrm{next}_m[l]$ 都随 $l$ 单调不减，因此 $\mathrm{maxnext}_k[l]$ 关于 $l$ 单调不减。这带来一个关键性质：对区间 $[L,R]$ 做 chmax 到 $x$ 时，由于区间内值单调不减，值为 $\ge x$ 的部分是一个后缀。只需：

二分/查找区间内第一个值 $\ge x$ 的位置 $r_0$ ；
把 $[L,r_0)$ 整段赋值为 $x$ （ $[r_0,R)$ 原本就 $\ge x$ ，无需改动）。

这样总操作数 $O(N)$ ，每个操作 $O(\log N)$ 。

实现方式：用 std::map 维护 $\mathrm{maxnext}$ 的分段常数表示：键为半开区间 $[l,r)$ ，值为该段常数。预处理为位置 $0..N$ （0-indexed，位置 $N$ 是恒为 $N$ 的哨兵，对计数贡献为 0）的初始段 $[i,i+1)\to i$ 。对每个区间 chmax：

split(x) 在位置 $x$ 处把所在段切开，保证边界存在；
在 $[L,R)$ 内按序删除所有值 $<x$ 的段，合并成 $[L,R')$ 赋值为 $x$ ，同时维护全段总和 sum。

每处理完一个 $k$ ， $\sum_{l=0}^{N}\mathrm{maxnext}_k[l]=\texttt{sum}$ ，于是

|S_k| = N(N+1)-\texttt{sum}

（ $N(N+1)$ 来自 $\sum_{l=0}^{N-1} N$ ，哨兵 $N$ 处贡献恒为 0），累加到答案。最终复杂度 $O(N\log N)$ 。

参考代码

#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<int> A(N);
    vector<vector<int>> pos(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        pos[A[i]].push_back(i);
    }

    // maxnext 的分段常数表示：key = 半开区间 [l, r)，value = 该段取值
    map<pair<int, int>, ll> seg;
    ll sum = 0;
    for (int i = 0; i <= N; i++) {   // 位置 0..N，N 为哨兵（恒为 N）
        seg[{i, i + 1}] = i;
        sum += i;
    }

    auto split = [&](int x) {
        // 确保位置 x 处存在段边界
        auto it = seg.lower_bound({x + 1, -1});   // 第一个 l > x 的段
        if (it == seg.begin()) return;
        --it;                                     // l <= x 的最后一个段
        pair<int, int> p = it->first;
        ll val = it->second;
        if (x <= p.first || p.second <= x) return;
        seg.erase(it);
        seg[{p.first, x}] = val;
        seg[{x, p.second}] = val;
    };

    ll ans = 0;
    for (int k = 0; k < N; k++) {
        vector<int> ris = pos[k];
        ris.push_back(N);
        for (size_t i = 0; i < ris.size(); i++) {
            int l = (i == 0 ? 0 : ris[i - 1] + 1);
            int r = ris[i] + 1;
            int x = ris[i];   // 区间 [l, r) 上 next_k[l] = x，做 chmax(x)
            split(l);
            split(r);
            // 删除 [l, r) 中值 < x 的段，合并为 [l, delr) 并赋值为 x
            int delr = l;
            auto it = seg.lower_bound({l, -1});
            while (it != seg.end()) {
                if (it->first.first >= r) break;  // 超出区间
                if (it->second >= x) break;       // 单调性：后续段都 >= x
                sum -= (ll)(it->first.second - it->first.first) * it->second;
                delr = it->first.second;
                it = seg.erase(it);
            }
            if (l < delr) {
                seg[{l, delr}] = x;
                sum += (ll)(delr - l) * x;
            }
        }
        ans += (ll)N * (N + 1) - sum;   // 第 k 步贡献的 |S_k|
    }

    cout << ans << "\n";
    return 0;
}

复杂度分析

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