AtCoder Beginner Contest 462 题解

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

比赛概览

本场整体难度中等偏易，A、B 两题为入门送分题。C 是排序后数"前缀最小值"的经典套路，D 是用差分数组数"同时在场人数"的扫描题，两者都值得初学者反复体会。E 是一道带奇偶性约束的路径费用最小化，分类讨论很巧妙，是全场最有思维含量的一题；F 是状态设计较灵活的 DP；G 则是容斥原理 + 多项式乘积（NTT）的综合题，区分度最高，适合进阶学习。

---

A - Secret Numbers

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_a

题目大意

给定一个由小写英文字母和数字组成的字符串 $S$（长度 $1\sim 50$）。把所有数字字符按原顺序取出并输出（若没有数字则输出空串）。

思路

逐字符遍历 $S$，判断每个字符是否为数字字符（即是否在 '0' 到 '9' 之间），是则追加到答案串末尾即可。在 C++ 中可用 c >= '0' && c <= '9' 判断，也可用 std::isdigit。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s, ans;
    cin >> s;
    for (char c : s)
        if (c >= '0' && c <= '9') ans += c;
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 参考实现：

print("".join(filter(str.isdigit, input())))

复杂度分析

• 时间复杂度：$O(|S|)$
• 空间复杂度：$O(|S|)$（答案字符串）

---

B - Gift

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_b

题目大意

$N$ 个人互送礼物，第 $i$ 个人给 $K_i$ 个人（编号 $A_{i,1}<A_{i,2}<\cdots<A_{i,K_i}$）送了礼物。对每个 $i$，输出所有"送礼物给第 $i$ 个人"的编号（升序）。

思路

用"逆邻接表"：把边"第 $i$ 个人送礼物给 $a$"改记为"$a$ 收到了来自 $i$ 的礼物"，即向 rec[a] 中追加 $i$。由于我们按 $i=1,2,\dots,N$ 的顺序处理，对固定的收礼人 $a$，其 rec[a] 中追加的送礼人编号天然递增，无需再排序。最后对每个 $i$ 输出 rec[i] 的长度与内容即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<vector<int>> rec(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            rec[a].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << rec[i].size();
        for (int x : rec[i]) cout << ' ' << x;
        cout << '\n';
    }
    return 0;
}

官方题解给出的 Python 参考实现：

n = int(input())
ans = [[] for _ in range(n)]
for i in range(n):
    a = list(map(int, input().split()))[1:]
    for c in a:
        ans[c - 1].append(i + 1)
for i in range(n):
    a = [len(ans[i])] + ans[i]
    print(*a)

复杂度分析

• 时间复杂度：$O(N+\sum_i K_i)$
• 空间复杂度：$O(N+\sum_i K_i)$

---

C - Not Covered Points

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_c

题目大意

平面上有 $N$ 个点，第 $i$ 个点坐标为 $(X_i,Y_i)$，其中 $X$ 坐标和 $Y$ 坐标各自是 $(1,2,\dots,N)$ 的一个排列。问有多少个 $i$，使得左下角为 $(0,0)$、右上角为 $(X_i,Y_i)$ 的轴平行矩形的**内部（不含边界）**不含任何一个给定点。

思路

由于 $X$、$Y$ 各自是排列，所以不存在两个点有相同的 $X$ 坐标或相同的 $Y$ 坐标。

矩形内部（不含边界）包含点 $j$ 当且仅当

$$0<X_j<X_i \quad\text{且}\quad 0<Y_j<Y_i.$$

所有坐标都在 $1\sim N$，故第一个条件 $0<X_j$ 恒成立，于是"点 $j$ 在矩形内部"等价于 $X_j<X_i$ 且 $Y_j<Y_i$。因此点 $i$ 满足题意当且仅当：不存在 $j$ 使得 $X_j<X_i$ 且 $Y_j<Y_i$，即

$$\forall j\neq i,\quad X_j<X_i \;\Rightarrow\; Y_j>Y_i.$$

把点按 $X$ 升序排序后，排序中第 $i$ 个点满足条件当且仅当它是 $Y$ 值的前缀严格最小值（比之前所有点的 $Y$ 都小）。维护前缀最小值 $mn$ 从左到右扫描：若当前 $Y_i<mn$，则 $i$ 计入答案并更新 $mn$。由于 $Y$ 是排列，不会出现相等，用严格小于即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> pts(n);
    for (int i = 0; i < n; i++) cin >> pts[i].first >> pts[i].second;
    sort(pts.begin(), pts.end());              // 按 X 升序
    int mn = n + 1, ans = 0;
    for (auto [x, y] : pts) {
        if (y < mn) {                          // y 是新的前缀严格最小值
            mn = y;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 参考实现：

import sys
input = sys.stdin.readline
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((x - 1, y - 1))
xy.sort()
min_val = n
ans = 0
for x, y in xy:
    min_val = min(min_val, y)
    ans += min_val == y
print(ans)

复杂度分析

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

---

D - Accomplice

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_d

题目大意

$N$ 个嫌疑人，第 $i$ 个在时刻 $S_i$ 进入宅邸、$T_i$ 离开，其余时间不在。案件在某个整数时刻 $x$ 开始，耗时 $D$，在 $x+D$ 完成；两名罪犯在案发全程都在宅邸内（允许恰好在开始时刻进入或完成时刻离开）。问有多少种"（两名罪犯的无序组合，案件开始时刻 $x$）"的组合是可能的。

思路

固定开始时刻 $t$。第 $i$ 个人可以作为罪犯，当且仅当他在 $[t,t+D]$ 全程在场，即

$$S_i\le t \quad\text{且}\quad t+D\le T_i \iff t\le T_i-D.$$

所以只有满足 $T_i-S_i\ge D$ 的人才可能在某个时刻作为罪犯，且他有效的开始时刻范围为整数区间 $[S_i,\;T_i-D]$。

令 $c_t$ 表示时刻 $t$ 可作罪犯的人数（即满足 $S_i\le t\le T_i-D$ 的 $i$ 的数量）。则时刻 $t$ 的两人组合数为

$$\binom{c_t}{2}=\frac{c_t(c_t-1)}{2},$$

答案即为

$$\sum_{t}\binom{c_t}{2}.$$

$t$ 的取值范围为 $1\le t\le \max T_i\le 10^6$。用差分数组维护 $c_t$：对每个满足 $T_i-S_i\ge D$ 的人，令 $\mathrm{diff}[S_i]+1$、$\mathrm{diff}[T_i-D+1]-1$，然后做一次前缀和即可得到每个时刻的 $c_t$。

注意两点：一是答案可能很大（最大约 $10^6\times\binom{2\times10^5}{2}\approx 2\times 10^{16}$），必须用 64 位整数；二是当 $D$ 很大、$T_i-D<S_i$ 时该人直接排除。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, D;
    cin >> N >> D;
    const int M = 1000000;                    // 最大时刻
    vector<long long> diff(M + 2, 0);
    for (int i = 0; i < N; i++) {
        int S, T;
        cin >> S >> T;
        if (T - S >= D) {                     // 可能成为罪犯
            diff[S] += 1;
            diff[T - D + 1] -= 1;
        }
    }
    long long c = 0, ans = 0;
    for (int t = 1; t <= M; t++) {
        c += diff[t];
        ans += c * (c - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 参考实现：

N, D = map(int, input().split())
M = 10**6 + 1
d = [0] * M
for i in range(N):
    S, T = map(int, input().split())
    if T - S >= D:
        d[S] += 1
        d[T - D + 1] -= 1
c, ans = 0, 0
for i in range(M):
    c += d[i]
    ans += c * (c - 1) // 2
print(ans)

复杂度分析

• 时间复杂度：$O(N+M)$，其中 $M=\max_i T_i\le 10^6$
• 空间复杂度：$O(M)$

---

E - Alternating Costs

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_e

题目大意

棋子从 $(0,0)$ 出发，每次可向上下左右四方向走一格。第 $k$ 步（$k\ge 1$）的费用取决于 $k$ 的奇偶性：$k$ 为奇数时水平走费用 $A$、垂直走费用 $B$；$k$ 为偶数时反过来（水平 $B$、垂直 $A$）。求到达 $(X,Y)$ 的最小总费用。$T$ 组数据。

思路

记 $f_{A,B}(X,Y)$ 为所求最小费用。先把棋盘整体沿坐标轴翻转，费用不变，因此可以假设 $X,Y\ge 0$。

情形一：$X+Y$ 为奇数。 每走一步 $x+y$ 的奇偶性都会翻转，所以到达 $(X,Y)$ 所需的步数 $m$ 满足 $m\equiv X+Y\pmod 2$；当 $X+Y$ 为奇数时 $m$ 为奇数，最后一步是"奇序号"步。对最优路径做翻转论证（把路径沿 $x=0,X$ 与 $y=0,Y$ 翻折后费用不变），可以令最后一步为从 $(X-1,Y)$ 水平走到 $(X,Y)$（费用 $A$），或从 $(X,Y-1)$ 垂直走到 $(X,Y)$（费用 $B$）。于是

$$f_{A,B}(X,Y)=\min\big(f_{A,B}(X-1,Y)+A,\; f_{A,B}(X,Y-1)+B\big),$$

从而把问题化归为 $X+Y$ 为偶数的情形（$X-1+Y$ 与 $X+Y-1$ 均为偶数）。当 $X=0$ 或 $Y=0$ 时上述式子会出现负坐标，公式依然成立（对应"先绕路多走几步、最后折回"的最优方案），代码中由闭式公式直接处理。

情形二：$X+Y$ 为偶数。 设步数为 $2K$，其中奇序号、偶序号各 $K$ 步。由对称性可再假设 $A\le B$（否则交换 $A,B$）、$X\le Y$（否则交换 $X,Y$）。

由于 $A\le B$，我们希望尽量让更多的步花费 $A$。花费 $A$ 的步只有两类：奇序号水平步和偶序号垂直步。对固定的 $K$（可行范围为 $\frac{X+Y}{2}\le K\le Y$），最小费用为

$$g(K)=2KA+(Y-K)(B-A).$$

直观理解：总共 $2K$ 步先全部按 $A$ 计费，得 $2KA$；再考虑至少有 $Y-K$ 步必须花费 $B$。原因是最多只有 $K$ 步"偶序号垂直步"可以花 $A$，而垂直方向需要净位移 $Y$，故至少有 $Y-K$ 步垂直移动（奇序号）不得不以 $B$ 计费。这个下界可以达到：安排 $Y-K$ 个奇序号步做垂直移动（费用 $B$），其余奇序号步做水平移动、所有偶序号步做垂直移动（费用 $A$），多出来的水平移动用"一来一回"的对子抵消即可，总费用恰为 $g(K)$。

$g(K)=2KA+(Y-K)(B-A)=K(3A-B)+Y(B-A)$ 是 $K$ 的线性函数，最小值必在可行区间的端点取得，所以只需比较

$$g\!\left(\frac{X+Y}{2}\right)=A(X+Y)+\frac{(Y-X)(B-A)}{2} \quad\text{与}\quad g(Y)=2AY.$$

当 $K>Y$ 时（即 $2K$ 步内可以全部用费用 $A$ 的步完成），增加 $K$ 只会使总费用每对增加 $2A$，最优点仍在 $K=Y$，已被上式覆盖。故偶数情形的答案即为上述两者的较小值。

汇总算法：先取 $X=|X|,\ Y=|Y|$；若 $X+Y$ 为奇数，递归地取 $\min\big(\text{solve}(X-1,Y)+A,\ \text{solve}(X,Y-1)+B\big)$；否则直接 $\text{solve}(X,Y)$。其中 $\text{solve}$ 内部再交换到 $A\le B,\ X\le Y$ 并返回 $\min\big(2AY,\ A(X+Y)+\frac{(Y-X)(B-A)}{2}\big)$。所有中间量都要用 64 位整数（$A(X+Y)$ 最大约 $2\times10^{18}$）。

参考代码

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

// 处理 X+Y 为偶数、且 |X|,|Y| 已归一化的情形（内部交换到 A<=B, X<=Y）
ll solve(ll a, ll b, ll x, ll y) {
    if (a > b) swap(a, b);
    if (x > y) swap(x, y);
    return min(2 * a * y, a * (x + y) + (b - a) * (y - x) / 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll A, B, X, Y;
        cin >> A >> B >> X >> Y;
        X = llabs(X);
        Y = llabs(Y);
        ll ans;
        if ((X + Y) & 1) {
            ans = min(solve(A, B, X - 1, Y) + A, solve(A, B, X, Y - 1) + B);
        } else {
            ans = solve(A, B, X, Y);
        }
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 参考实现：

def solve(a, b, x, y):
    if a > b:
        a, b = b, a
    if x > y:
        x, y = y, x
    return min(2 * a * y, a * (x + y) + (b - a) * (y - x) // 2)

for _ in range(int(input())):
    a, b, x, y = map(int, input().split())
    x, y = abs(x), abs(y)
    if (x + y) % 2 == 1:
        print(min(solve(a, b, x - 1, y) + a, solve(a, b, x, y - 1) + b))
    else:
        print(solve(a, b, x, y))

复杂度分析

• 时间复杂度：$O(T)$（每组 $O(1)$）
• 空间复杂度：$O(1)$

---

F - More ABC

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_f

题目大意

给定大写字母串 $S$，每次可以把一个字符替换成任意大写字母。问能否通过若干次替换，使 $S$ 中"ABC"作为子串的出现次数恰好增加 $K$；若能，输出最少替换次数，否则输出 $-1$。$T$ 组数据，所有 $S$ 的总长度不超过 $3\times10^5$，$1\le K\le 10$。

思路

这是"从左往右逐位确定最终串"的 DP。记 $f(T)$ 为串 $T$ 中"ABC"的出现次数。

设 $dp[i][j]$（$0\le i\le N$，$0\le j\le K$）表示：考虑 $S$ 的前 $i$ 个字符，通过替换得到 $S'$ 的前 $i$ 个字符，使 $f(S'_1\cdots S'_i)-f(S_1\cdots S_i)\ge j$ 所需的最少替换次数，不可能则为 $+\infty$。初始 $dp[i][0]=0$，$dp[0][j]=+\infty\ (j\ge1)$，答案为 $dp[N][K]$。

在第 $i$ 个位置，新出现的"ABC"只可能以 $i$ 结尾，即窗口 $S'_{i-2}S'_{i-1}S'_i$。分两种情况讨论（$i<3$ 时不存在窗口，只走第二种）：

情形 1：$S'_{i-2}S'_{i-1}S'_i=\texttt{ABC}$。 此时 $S'_{i-2}=\texttt A$、$S'_{i-1}=\texttt B$，故任何以 $i-2$ 或 $i-1$ 结尾的窗口都不可能是"ABC"，于是

$$f(S'_1\cdots S'_i)=f(S'_1\cdots S'_{i-3})+1.$$

原串中"以 $i-2,\ i-1,\ i$ 结尾"的 ABC 个数为 $X_i=f(S_1\cdots S_i)-f(S_1\cdots S_{i-3})\in\{0,1\}$（这三个窗口两两重叠，最多出现一个）。于是需满足

$$f(S'_1\cdots S'_{i-3})-f(S_1\cdots S_{i-3})=j-1+X_i.$$

再设 $Y_i$ 为把 $S_{i-2}S_{i-1}S_i$ 改成"ABC"所需替换次数（$0\le Y_i\le 3$），得到转移

$$dp[i][j]\ \longleftarrow\ dp[i-3][j-1+X_i]+Y_i.$$

情形 2：$S'_{i-2}S'_{i-1}S'_i\ne\texttt{ABC}$。 可以假设第 $i$ 个字符没有被修改。理由：若 $S'_i$ 被修改而窗口仍不是"ABC"，那么把 $S'_i$ 换回原字符 $S_i$，$f(S'_1\cdots S'_{i-1}S_i)\le f(S'_1\cdots S'_{i-1}S'_i)$（以 $i$ 结尾的窗口从"非 ABC"变回"非 ABC"，不会新增出现次数），替换次数更少，矛盾。故 $S'_i=S_i$，此时

$$f(S'_1\cdots S'_i)=f(S'_1\cdots S'_{i-1}).$$

设 $Z_i=f(S_1\cdots S_i)-f(S_1\cdots S_{i-1})\in\{0,1\}$（即原串中 $S_{i-2}S_{i-1}S_i$ 是否为"ABC"），则需满足

$$f(S'_1\cdots S'_{i-1})-f(S_1\cdots S_{i-1})=j+Z_i,$$

得到转移

$$dp[i][j]\ \longleftarrow\ dp[i-1][j+Z_i].$$

综上

$$dp[i][j]=\min\big(dp[i-3][j-1+X_i]+Y_i,\ dp[i-1][j+Z_i]\big),$$

下标越界的一项忽略即可（$j-1+X_i\ge 0$ 恒成立，因为 $j\ge1$；$j+Z_i>K$ 时该状态不可能通向最优解）。$Z_i$ 可直接判断原串窗口是否为"ABC"，$X_i=Z_{i-2}+Z_{i-1}+Z_i$，$Y_i$ 数一数窗口内三个位置与"A、B、C"的失配个数，均可 $O(1)$ 预处理。若 $dp[N][K]=+\infty$ 输出 $-1$。

参考代码

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

#define INF (int)1e9

int main() {
    int t, n, k;
    string s;
    cin >> t;
    while (t--) {
        cin >> s;
        cin >> k;
        n = (int)s.size();
        vector<int> x(n + 1), y(n + 1), z(n + 1);
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));

        for (int i = 3; i <= n; i++) {                    // 预处理 Y_i, Z_i, X_i
            if (s[i - 3] != 'A') y[i]++;
            if (s[i - 2] != 'B') y[i]++;
            if (s[i - 1] != 'C') y[i]++;
            if (y[i] == 0) z[i] = 1;                      // 原串窗口 S[i-2..i] 是 ABC
            for (int j = 0; j < 3; j++)
                if (i + j <= n) x[i + j] += z[i];         // x[m] = Z_{m-2}+Z_{m-1}+Z_m
        }

        for (int j = 1; j <= k; j++) dp[0][j] = INF;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = INF;
                if (j + z[i] <= k)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j + z[i]]);          // 情形 2
                if (i >= 3)
                    dp[i][j] = min(dp[i][j], dp[i - 3][j - 1 + x[i]] + y[i]); // 情形 1
            }
        }
        cout << (dp[n][k] >= INF ? -1 : dp[n][k]) << '\n';
    }
    return 0;
}

（官方题解给出的即为上述 C++ 实现，未提供独立的官方 Python。）

复杂度分析

• 时间复杂度：$O(|S|\cdot K)$
• 空间复杂度：$O(|S|\cdot K)$，可将 $dp$ 滚动优化至 $O(K)$

---

G - Completely Wrong

题目链接：https://atcoder.jp/contests/abc462/tasks/abc462_g

题目大意

箱中有 $N$ 个球，球 $i$ 的颜色为 $C_i$。第 $k$ 次操作：从箱中均匀随机摸出一个球并丢弃，若摸出的球颜色恰为 $G_k$ 则得 $1$ 分。求 $N$ 次操作后总分为 $0$ 的概率，对 $998244353$ 取模。

思路

摸球的顺序等价于随机排列 $P=(P_1,\dots,P_N)$（$P_k$ 表示第 $k$ 次摸出的球），总分 $=|\{k: C_{P_k}=G_k\}|$。所求即

$$\Pr\big[\forall k,\ C_{P_k}\ne G_k\big].$$

记 $S_i=\{P: C_{P_i}=G_i\}$。由容斥原理，

$$\left|\bigcap_{i=1}^N\overline{S_i}\right| =\sum_{A\subseteq\{1,\dots,N\}}(-1)^{|A|}\left|\bigcap_{i\in A}S_i\right|,$$

答案 $=\frac{1}{N!}\left|\bigcap_i\overline{S_i}\right|$。

对固定的集合 $A$，令 $X_k=|\{i:C_i=k\}|$，$Y_k=|\{i:G_i=k\}|$，$D_k=|\{i\in A:G_i=k\}|$。若某颜色 $k$ 满足 $D_k>X_k$，则 $\bigcap_{i\in A}S_i=\varnothing$；否则：

• 从 $Y_k$ 个满足 $G_i=k$ 的位置中选出 $D_k$ 个放进 $A$：$\binom{Y_k}{D_k}$ 种；
• 从 $X_k$ 个颜色为 $k$ 的球中选出 $D_k$ 个并一一分配给这些位置：$\binom{X_k}{D_k}D_k!$ 种；
• 其余 $N-|A|$ 个位置任意排列剩余球：$(N-|A|)!$ 种。

于是贡献为 $\prod_{k}\binom{X_k}{D_k}\binom{Y_k}{D_k}D_k!\cdot(N-|A|)!$，乘上符号 $(-1)^{|A|}$ 后求和。令 $f_k(x)=\sum_{j\ge0}(-1)^j\binom{X_k}{j}\binom{Y_k}{j}j!\,x^j$，$f(x)=\prod_k f_k(x)=\sum_i c_i x^i$，则答案可写成

$$\frac{1}{N!}\sum_{i\ge0}c_i\,(N-i)!.$$

实现时：$f_k$ 的次数为 $\min(X_k,Y_k)$，所有 $f_k$ 的次数之和不超过 $\sum_k X_k=N$。用优先队列每次取出两个次数最小的多项式做 NTT 乘法后放回，总复杂度 $O(N\log^2 N)$。模数 $998244353=119\cdot2^{23}+1$，原根为 $3$，很适合做 NTT。注意若每个颜色都有 $\min(X_k,Y_k)=0$，则 $f(x)\equiv1$，答案为 $1$。

参考代码

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

const ll MOD = 998244353;
const ll ROOT = 3;

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;
}

void ntt(vector<ll>& a, bool inv) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll wlen = modpow(ROOT, (MOD - 1) / len);
        if (inv) wlen = modpow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = w * wlen % MOD;
            }
        }
    }
    if (inv) {
        ll inv_n = modpow(n, MOD - 2);
        for (auto& x : a) x = x * inv_n % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

struct Cmp {
    bool operator()(const vector<ll>& a, const vector<ll>& b) const {
        return a.size() > b.size();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> C(N), G(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    for (int i = 0; i < N; i++) cin >> G[i];

    vector<int> X(N + 1), Y(N + 1);
    for (int i = 0; i < N; i++) { X[C[i]]++; Y[G[i]]++; }

    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;
    auto comb = [&](int n, int k) -> ll {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
    };

    priority_queue<vector<ll>, vector<vector<ll>>, Cmp> pq;
    for (int k = 1; k <= N; k++) {
        int m = min(X[k], Y[k]);
        if (m == 0) continue;          // f_k(x) = 1，跳过
        vector<ll> f(m + 1);
        for (int j = 0; j <= m; j++) {
            ll coef = comb(X[k], j) * comb(Y[k], j) % MOD * fact[j] % MOD;
            if (j & 1) coef = (MOD - coef) % MOD;
            f[j] = coef;
        }
        pq.push(move(f));
    }
    if (pq.empty()) { cout << 1 << '\n'; return 0; }

    while (pq.size() > 1) {
        vector<ll> a = pq.top(); pq.pop();
        vector<ll> b = pq.top(); pq.pop();
        pq.push(multiply(a, b));
    }
    vector<ll> f = pq.top();

    ll ans = 0;
    for (int i = 0; i < (int)f.size(); i++)
        ans = (ans + f[i] * fact[N - i]) % MOD;
    ans = ans * modpow(fact[N], MOD - 2) % MOD;
    cout << ans << '\n';
    return 0;
}

（本题官方题解仅给出了容斥 + 多项式乘积的算法与复杂度分析，未提供参考代码；上述代码为依据该思路实现并验证过的版本。）

复杂度分析

• 时间复杂度：$O(N\log^2 N)$（多项式乘积，采用优先队列合并最小次数多项式 + NTT）
• 空间复杂度：$O(N)$