AtCoder Beginner Contest 422 题解

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

AtCoder Beginner Contest 422 题解

项目	内容
比赛时间	2025-09-07
比赛链接	https://atcoder.jp/contests/abc422
题目数量	A–G 共 7 题

比赛概览

本场整体难度中等偏上，A–D 比较基础（其中 D 需要一点逆向思维与不变量论证），E–G 具有较强区分度。涉及的主要知识点包括：格式化输入与条件分支（A）、网格模拟与"哨兵"技巧（B）、贪心与构造性上界论证（C）、逆向构造与归纳证明（D）、随机化几何算法（E）、分层图上的 DP 建模（F）、以及生成函数与 NTT 卷积（G）。其中 E（随机化）、F（图上的费用建模）、G（生成函数）三题尤其值得仔细掌握。

A - Stage Clear

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_a

题目大意

游戏共有 $8$ 个世界、每个世界 $8$ 个关卡，关卡按顺序排列：第 $i$ 世界第 $j$ 关（ $1\le j<8$ ）的下一关是同世界第 $j+1$ 关；第 $i$ 世界第 $8$ 关（ $i<8$ ）的下一关是第 $i+1$ 世界第 $1$ 关；8-8 是最后一关。给定当前关卡名 $S$ （保证不是 8-8），输出下一关的关卡名。

思路

把关卡名 $S$ 拆成世界编号 $i$ 和关卡编号 $j$ 两个整数即可：

若 $j<8$ ，下一关是 $(i,\ j+1)$ ；
若 $j=8$ ，说明这是当前世界的最后一关，下一关是 $(i+1,\ 1)$ 。

解析字符串有两种常见做法。一是直接操作字符串：读入整个字符串 $S$ ，若最后一个字符是 '8'，则把第一个字符加 $1$ 、最后一个字符改成 '1'；否则把最后一个字符加 $1$ 。二是利用 C 的 scanf 格式化输入：scanf("%d-%d", &a, &b) 会自动跳过中间的 -，直接得到两个整数，更简洁。

边界情况：题目保证 $S$ 不是 8-8，所以" $i=8$ 且 $j=8$ "的情况不会出现，无需额外处理；但我们仍用 if (j == 9)（或 j > 8）的形式来处理进位，即使出现也不会越界。

参考代码

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

int main() {
    int i, j;
    scanf("%d-%d", &i, &j);   // 格式化输入，自动跳过 '-' 号
    ++j;
    if (j == 9) {             // 本世界最后一关：进入下一世界第 1 关
        ++i;
        j = 1;
    }
    printf("%d-%d\n", i, j);
    return 0;
}

官方题解给出了一种直接操作字符串的写法，同样干净：

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

int main() {
    string S;
    cin >> S;
    if (S[2] == '8') {   // 最后一个字符是 '8'
        S[0] += 1;       // 世界号加 1
        S[2] = '1';      // 关卡号重置为 1
    } else {
        S[2] += 1;       // 关卡号加 1
    }
    cout << S << '\n';
    return 0;
}

a, b = map(int, input().split('-'))
b += 1
if b > 8:
    a += 1
    b = 1
print(f"{a}-{b}")

复杂度分析

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

B - Looped Rope

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_b

题目大意

有一个 $H\times W$ 的网格，第 $i$ 行第 $j$ 列的格子记作 $(i,j)$ 。每个格子为白色（.）或黑色（#）。判断网格是否满足以下条件：对每个黑色格子，与其上下左右相邻的黑色格子个数为 $2$ 或 $4$ 。

思路

条件只对黑格提出要求，白格不限。因此直接枚举所有格子：若 $(i,j)$ 是黑格，就统计四个方向（ $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ ）中黑格的个数 $c$ ，若 $c\notin\{2,4\}$ ，立即输出 No；若所有黑格都满足，输出 Yes。没有任何黑格时条件自然成立，输出 Yes。

实现技巧——哨兵（sentinel）：判断四方向时最麻烦的是越界（比如左上角的格子只有两个邻居）。我们可以在原网格四周再围一圈白色格子，即开一个 $(H+2)\times(W+2)$ 的数组，边框全部为 .，把原网格填进中间。这样任何格子的四个方向邻居都一定存在，无需判断是否越界，代码更简洁。

需要注意"相邻"的定义是 $|i-k|+|j-l|=1$ ，即只考虑上下左右四个格子，不含斜对角。

参考代码

#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> field(H + 2, string(W + 2, '.'));
    for (int i = 1; i <= H; ++i) {
        string S;
        cin >> S;
        field[i] = "." + S + ".";
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (field[i][j] != '#') continue;
            int cnt = 0;
            for (int d = 0; d < 4; ++d) {
                if (field[i + dx[d]][j + dy[d]] == '#') ++cnt;
            }
            if (cnt != 2 && cnt != 4) {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << "Yes\n";
    return 0;
}

H, W = map(int, input().split())
field = ['.' * (W + 2)] + ['.' + input() + '.' for _ in range(H)] + ['.' * (W + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if field[i][j] == '#':
            cnt = 0
            for ni, nj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                cnt += (field[ni][nj] == '#')
            if cnt != 2 and cnt != 4:
                print("No")
                exit()
print("Yes")

复杂度分析

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

C - AtCoder AAC Contest

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_c

题目大意

Takahashi 有 $n_A$ 个字母 A、 $n_B$ 个字母 B、 $n_C$ 个字母 C。每举办一场比赛需要恰好 $3$ 个字母： $1$ 个 A、 $1$ 个 C，外加任意 $1$ 个字母（可以是 A、B 或 C）。给定 $T$ 组询问，每组求最多能举办的比赛场数。

思路

设答案为 $\text{ans}$ 。先找上界：

每场比赛都要用 $1$ 个 A，所以 $\text{ans}\le n_A$ ；
每场比赛都要用 $1$ 个 C，所以 $\text{ans}\le n_C$ ；
每场比赛用 $3$ 个字母，所以 $\text{ans}\le \left\lfloor\dfrac{n_A+n_B+n_C}{3}\right\rfloor$ 。

因此

X := \min\left\{n_A,\ n_C,\ \left\lfloor\frac{n_A+n_B+n_C}{3}\right\rfloor\right\}

是答案的一个上界。

接下来证明 $X$ 场一定可以办到（构造性论证）：因为 $X\le n_A$ 且 $X\le n_C$ ，我们先取出 $X$ 个 A 和 $X$ 个 C，配成 $X$ 对" $(A,C)$ "。剩余字母数为 $n_A+n_B+n_C-2X$ 。由 $X\le \lfloor (n_A+n_B+n_C)/3\rfloor$ 得 $3X\le n_A+n_B+n_C$ ，故

n_A+n_B+n_C-2X \ge X,

即剩余字母至少还有 $X$ 个，足以给每一对 $(A,C)$ 补上第三个任意字母。于是 $X$ 场可达，答案就是 $X$ 。

易错点： $n_A+n_B+n_C$ 最大为 $3\times 10^9$ ，超过 $32$ 位有符号整数的上限，因此求和要用 64 位整数（long long）。

参考代码

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

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

    int T;
    cin >> T;
    while (T--) {
        long long a, b, c;
        cin >> a >> b >> c;
        cout << min({a, c, (a + b + c) / 3}) << '\n';
    }
    return 0;
}

复杂度分析

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

D - Least Unbalanced

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_d

题目大意

对长度为 $2^N$ 的非负整数序列 $A$ ，定义其 imbalance 为如下过程得到的值：初始 $X=0$ ；重复 $N$ 次：先更新 $X\gets\max(X,\ \max(A)-\min(A))$ ，再把 $A$ 的相邻元素两两配对求和，得到长度减半的新序列。给定 $K$ ，请在"长度为 $2^N$ 且元素和为 $K$ "的所有序列中构造一个使 imbalance 最小的序列，输出最小 imbalance 及该序列。

思路

关键观察：题目中的"配对求和"过程是可逆的。 一个数 $a$ 是由两个数 $p,q$ （ $p+q=a$ ）配对求和得到的。反过来，从"长度 1"的序列 $[K]$ 出发逆向构造：每步把当前层的每个元素 $a$ 拆成两个和为 $a$ 的数。为了尽量均衡，自然拆成

\left\lfloor \frac a2 \right\rfloor,\qquad \left\lceil \frac a2 \right\rceil \left(= a-\left\lfloor\frac a2\right\rfloor\right).

重复 $N$ 次后得到长度 $2^N$ 、和为 $K$ 的序列。而 imbalance 计算过程中出现的每一层数组，正是构造过程中的每一层（顺序相反）。因此该序列的 imbalance 等于构造各层 $\max-\min$ 的最大值。

引理（不变量）：若某一层所有元素的 $\max-\min\le 1$ ，即所有元素只取 $m$ 或 $m+1$ 两种值，那么拆分后仍然满足 $\max-\min\le 1$ 。

证明：对 $m$ 拆分得到 $\{\lfloor m/2\rfloor,\lceil m/2\rceil\}$ ，两者差至多 $1$ ；对 $m+1$ 同理。全体拆分结果组成的集合是

\left\{\left\lfloor\frac m2\right\rfloor,\ \left\lceil\frac m2\right\rceil,\ \left\lfloor\frac{m+1}{2}\right\rfloor\right\},

因为 $\lfloor (m+1)/2\rfloor = \lceil m/2\rceil$ 。而

\left\lceil\frac{m+1}{2}\right\rceil - \left\lfloor\frac m2\right\rfloor = 1

（ $m=2q$ 时为 $q+1-q=1$ ； $m=2q+1$ 时亦为 $q+1-q=1$ ），所以拆分后 $\max-\min\le 1$ 。初始层 $[K]$ 的 $\max-\min=0$ ，归纳知所有层都满足，故构造序列的 imbalance $\le 1$ 。

下界：

若 $2^N \mid K$ ，令所有 $2^N$ 个元素都等于 $K/2^N$ ，则每一层都是全等序列，imbalance $=0$ ，这是绝对最小值。
若 $2^N\nmid K$ ，imbalance 不可能为 $0$ ：因为 imbalance $=0$ 意味着原序列所有元素相等，即 $K/2^N$ 必须是整数，与假设矛盾。所以最小 imbalance 至少为 $1$ ，而上述构造恰好达到 $1$ ，故为最优。

实现：vector<long long> ans{K}，重复 $N$ 次：对 ans 中每个元素 $a$ ，加入 a/2 和 a - a/2。最后输出 max(ans)-min(ans) 以及整个 ans。注意 $N=20$ 时 $2^N=1048576$ ，用 long long 存放中间值以避免任何溢出顾虑。

参考代码

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

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

    int N, K;
    cin >> N >> K;

    vector<long long> ans{K};
    for (int t = 0; t < N; ++t) {
        vector<long long> nxt;
        nxt.reserve(ans.size() * 2);
        for (long long a : ans) {
            nxt.push_back(a / 2);          // floor(a/2)
            nxt.push_back(a - a / 2);      // ceil(a/2)
        }
        ans = move(nxt);
    }

    long long mx = *max_element(ans.begin(), ans.end());
    long long mn = *min_element(ans.begin(), ans.end());
    cout << mx - mn << '\n';
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

复杂度分析

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

E - Colinear

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_e

题目大意

平面上有 $N$ 个点（ $N$ 为奇数， $3\le N\le 5\times 10^5$ ，坐标互异）。判断是否存在一条直线经过超过一半的点；若存在，输出该直线 $ax+by+c=0$ 的整数系数 $a,b,c$ （满足 $-10^{18}\le a,b,c\le 10^{18}$ ）。

思路

为什么想到随机化？ 若存在满足条件的直线 $L$ ，则 $L$ 上至少有 $(N+1)/2$ 个点（ $N$ 为奇数）。随机独立地选取两个点 $p_1,p_2$ ，它们同时落在 $L$ 上的概率为

\frac{\frac{N+1}{2}}{N}\cdot \frac{\frac{N+1}{2}-1}{N-1}=\frac{N+1}{4N}>\frac14.

而一旦两点都在 $L$ 上，过这两点的直线就是 $L$ （两点确定一条直线）。于是"随机取两点 → 检验过这两点的直线是否穿过超过一半的点"这个试验，在答案存在时每次成功的概率超过 $1/4$ 。单次试验只有 $O(N)$ 的代价，重复 $T$ 次即可把失败概率压到任意小：

P(\text{失败}) \le \left(1-\frac{N+1}{4N}\right)^T \le \left(\frac34\right)^T.

取 $T=100$ 时失败概率约为 $(3/4)^{100}\approx 3.2\times 10^{-13}$ ，可忽略不计。

直线的表示与共线判定。 过 $(x_1,y_1)$ 、 $(x_2,y_2)$ 两点的直线可写成

(y_1-y_2)x+(x_2-x_1)y+x_1y_2-x_2y_1=0,

即取 $a=y_1-y_2,\ b=x_2-x_1,\ c=x_1y_2-x_2y_1$ 。判定点 $(x_k,y_k)$ 是否在直线上，只需检查 $a x_k+b y_k+c=0$ （整数运算，不要用浮点）。关于溢出： $|x|,|y|\le 10^8$ ，故 $|a|,|b|\le 2\times 10^8$ ， $|c|\le 2\times 10^{16}$ ；求值过程中 $a x_k$ 的绝对值不超过 $2\times 10^{16}$ ，三者之和不超过 $6\times 10^{16}$ ，远小于 64 位有符号整数上限 $9.2\times 10^{18}$ ，用 long long 安全。

边界与易错点：

随机取点要保证 $i\ne j$ （点互异，故坐标不同）。
判断"超过一半"用 num * 2 > N（ $N$ 为奇数，等价于 $num \ge (N+1)/2$ ）。
若 $T$ 次试验都没找到，输出 No。
本算法是蒙特卡洛随机化算法，存在极小概率误判；AtCoder 没有 hack 环节，固定随机种子即可；若在可 hack 的平台（如 Codeforces），应改用 random_device 或 chrono 产生种子。

参考代码

#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<ll> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    mt19937_64 rng(58);
    const int T = 100;
    for (int t = 0; t < T; ++t) {
        int i, j;
        do {
            i = rng() % N;
            j = rng() % N;
        } while (i == j);

        ll a = Y[i] - Y[j];
        ll b = X[j] - X[i];
        ll c = X[i] * Y[j] - X[j] * Y[i];

        ll num = 0;
        for (int k = 0; k < N; ++k) {
            num += (a * X[k] + b * Y[k] + c == 0);
        }
        if (num * 2 > N) {   // 超过一半
            cout << "Yes\n";
            cout << a << ' ' << b << ' ' << c << '\n';
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

复杂度分析

时间复杂度： $O(TN)$ （ $T=100$ ，最坏约 $5\times 10^7$ 次运算）
空间复杂度： $O(N)$

F - Eat and Ride

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_f

题目大意

给定 $N$ 个点、 $M$ 条边的连通无向图，顶点 $v$ 有点权 $W_v$ 。Takahashi 从顶点 $1$ 出发（初始体重为 $0$ ），每次访问顶点 $v$ 体重增加 $W_v$ ；每经过一条边，消耗"当前体重"等量的燃料。对每个顶点 $i$ ，求到达顶点 $i$ 所需的最小燃料。

思路

问题转化。 设从 $1$ 到 $i$ 的一条路径为 $v_1=1,v_2,\dots,v_k=i$ 。经过边 $(v_s,v_{s+1})$ 时消耗的是已访问顶点体重之和 $\sum_{t=1}^{s} W_{v_t}$ ，因此总燃料为

\sum_{s=1}^{k-1}\sum_{t=1}^{s} W_{v_t}=\sum_{s=1}^{k}(k-s)\,W_{v_s}.

即顶点 $v_s$ 的贡献等于"离开它之后还要经过的边数"乘以 $W_{v_s}$ （最后一个顶点贡献为 $0$ ）。

由此得到等价的"门票"模型：Takahashi 出发时带着若干张票（每张票对应一条尚待经过的边）。

访问顶点 $v$ 时，若手里还剩 $n$ 张票，则消耗 $n\cdot W_v$ 燃料；
每经过一条边，用掉一张票。

到达顶点 $i$ 时恰好剩 $0$ 张票，总花费最小化。

最优路径是简单路径。 若一条走法重复访问了某个顶点 $v$ ，删去从第一次访问 $v$ 到最后一次访问 $v$ 之间的闭环段，会得到一条更短的合法走法；由于所有 $W_v\ge 1$ 且所有系数都为正，删环后花费严格减少。故最优路径至多包含 $N$ 个顶点，最多需要 $N-1$ 张票。

分层 DP。 设 $f_t[v]$ 表示"到达顶点 $v$ ，且之后还剩 $t$ 条边要走"时的最小已付燃料（已付部分包含所有已经离开过的顶点，不含 $v$ 本身）。边界： $f_t[1]=0$ （从顶点 $1$ 出发、尚未离开，任何票数都可行）。转移：从 $u$ 沿边走到 $v$ 时，离开 $u$ 时还剩 $t$ 条边，需付 $t\cdot W_u$ ，到 $v$ 后剩 $t-1$ 条边：

f_{t-1}[v]=\min\Bigl(f_{t-1}[v],\ f_t[u]+t\cdot W_u\Bigr).

答案就是 $f_0[i]$ 。状态图是一张 DAG（票数严格递减），按 $t$ 从 $N-1$ 递减到 $1$ 逐层 DP 即可，每层只需一维数组。

实现细节： 每层先复制上一层的 $f_{t}$ ，再初始化本层 $f_{t-1}$ 为 $+\infty$ 并令 $f_{t-1}[1]=0$ ，然后对每条无向边做双向松弛。自环边不会产生更好的值（ $t\ge1,\ W\ge1$ ），可放心保留。答案可能超过 $2^{32}$ （见样例 2），务必使用 64 位整数。

参考代码

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

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

    int N, M;
    cin >> N >> M;
    vector<ll> W(N);
    for (auto& x : W) cin >> x;

    vector<pair<int, int>> edges(M);
    for (auto& [u, v] : edges) {
        cin >> u >> v;
        --u; --v;
    }

    const ll INF = (1LL << 62);
    vector<ll> dp(N, INF), prev(N, INF);
    dp[0] = 0;                        // f_{N-1}[1] = 0

    for (int t = N - 1; t >= 1; --t) {
        prev = dp;                    // prev = f_t
        fill(dp.begin(), dp.end(), INF);
        dp[0] = 0;                    // f_{t-1}[1] = 0
        for (auto [u, v] : edges) {
            dp[v] = min(dp[v], prev[u] + t * W[u]);   // 离开 u 时还剩 t 条边
            dp[u] = min(dp[u], prev[v] + t * W[v]);
        }
    }

    for (int v = 0; v < N; ++v) cout << dp[v] << '\n';  // dp = f_0
    return 0;
}

复杂度分析

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

G - Balls and Boxes

题目链接：https://atcoder.jp/contests/abc422/tasks/abc422_g

题目大意

给定 $N,A,B,C$ 。现有 3 个盒子，要求把 $N$ 个球全部放入：盒子 1 的球数是 $A$ 的倍数、盒子 2 的球数是 $B$ 的倍数、盒子 3 的球数是 $C$ 的倍数。求方案数模 $998244353$ ，其中：

Problem 1： $N$ 个球彼此不可区分，两种放法不同当且仅当存在一个盒子球数不同；
Problem 2： $N$ 个球被编号 $1..N$ ，彼此可区分，两种放法不同当且仅当存在一个球的归属盒子不同。

思路

这是一道生成函数（GF）入门题。核心思想：把"一个组合对象"编码成某个多项式中的一项，用多项式的乘除来对应组合结构的拼合。

Problem 1：普通生成函数（OGF）。 球不可区分，则一种放法只由三元组 $(i,j,k)$ 决定，其中 $i+j+k=N$ ，且 $A\mid i,\ B\mid j,\ C\mid k$ ，方案数就是这样的三元组个数。令

F_A(x)=\sum_{i\ge 0} x^{iA}=1+x^A+x^{2A}+\cdots,

表示"盒子 1 装了 $i$ 个球"这一贡献记为 $x^i$ （ $i$ 遍历 $A$ 的倍数）。三个盒子的整体方案对应三个多项式的乘积，故答案是

\text{ans}_1=[x^N]\,F_A(x)\,F_B(x)\,F_C(x).

Problem 2：指数型生成函数（EGF）。 球可区分，不能直接用普通卷积。令

G_A(x)=\sum_{i\ge 0}\frac{x^{iA}}{(iA)!},

（ $B,C$ 类似）。EGF 的乘法对应"带标号对象的拼接"：把 $N$ 个标号球分成盒子 1、2、3，恰好对应

N!\,[x^N]\left(\frac{x^a}{a!}\frac{x^b}{b!}\frac{x^c}{c!}\right)=\frac{N!}{a!b!c!}=\binom{N}{a}\binom{N-a}{b},

即"先选 $a$ 个球给盒子 1，再从剩下 $N-a$ 个中选 $b$ 个给盒子 2，其余给盒子 3"。故

\text{ans}_2=N!\,[x^N]\,G_A(x)\,G_B(x)\,G_C(x).

计算：NTT 卷积。 模数 $998244353=119\cdot 2^{23}+1$ 是 NTT 友好素数，原根为 $3$ 。预处理阶乘与阶乘逆元；构造三个多项式的前 $N+1$ 项（ $i\%A==0$ 时系数为 $1$ 或 $\text{invfac}[i]$ ），将它们统一补零到长度 $sz\ge 3N+1$ （ $2$ 的幂），各做一次 NTT，频域逐点相乘，再逆变换，取第 $N$ 项系数即可。因为 $3N<sz$ ，不存在循环卷积的环绕（wraparound），得到的正是乘积多项式的系数。若 $A,B,C$ 中某个大于 $N$ ，对应多项式只有第 $0$ 项非零，代码天然正确处理。

正确性要点： Problem 1 用 OGF 是因为"不可区分"只关心数量；Problem 2 用 EGF 是因为"可区分"需要组合数系数 $\binom{N}{a}\binom{N-a}{b}$ ，而 EGF 卷积恰好产生这个因子。两类问题在生成函数层面被统一为"三次多项式卷积后取 $[x^N]$ "。

参考代码

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

const ll MOD = 998244353;
const ll ROOT = 3;   // MOD 的原根

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

void ntt(vector<ll>& a, bool invert) {
    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 (invert) 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];
                ll 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 (invert) {
        ll inv_n = modpow(n, MOD - 2);
        for (ll& x : a) x = x * inv_n % MOD;
    }
}

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

    int N, A, B, C;
    cin >> N >> A >> B >> C;

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

    // 三个 N 次多项式相乘，最高次数 3N，取不小于 3N+1 的 2 的幂
    int sz = 1;
    while (sz < 3 * N + 1) sz <<= 1;

    // Problem 1：OGF 乘积的 [x^N]
    vector<ll> f1(sz), f2(sz), f3(sz);
    for (int i = 0; i <= N; ++i) {
        if (i % A == 0) f1[i] = 1;
        if (i % B == 0) f2[i] = 1;
        if (i % C == 0) f3[i] = 1;
    }
    ntt(f1, false); ntt(f2, false); ntt(f3, false);
    for (int i = 0; i < sz; ++i) f1[i] = f1[i] * f2[i] % MOD * f3[i] % MOD;
    ntt(f1, true);
    cout << f1[N] << '\n';

    // Problem 2：EGF 乘积的 [x^N] * N!
    vector<ll> g1(sz), g2(sz), g3(sz);
    for (int i = 0; i <= N; ++i) {
        if (i % A == 0) g1[i] = invfac[i];
        if (i % B == 0) g2[i] = invfac[i];
        if (i % C == 0) g3[i] = invfac[i];
    }
    ntt(g1, false); ntt(g2, false); ntt(g3, false);
    for (int i = 0; i < sz; ++i) g1[i] = g1[i] * g2[i] % MOD * g3[i] % MOD;
    ntt(g1, true);
    cout << g1[N] * fac[N] % MOD << '\n';

    return 0;
}

（若使用 AC Library，可直接用 atcoder::convolution 替换自写的 NTT，结果一致。）

复杂度分析

时间复杂度： $O(N\log N)$ （常数次 NTT，每次长度为 $O(N)$ 的 2 的幂）
空间复杂度： $O(N)$