AtCoder Beginner Contest 439 题解

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

比赛概览

本场是 2026 新年第一场 ABC，多道题与数字 $2026$ 呼应（A 题在 $N=11$ 时答案为 $2026$，B 题样例为 $2026$，C 题标题就是 $2026$）。整体难度分布均匀：A、B 为签到/入门题；C 需要"反过来枚举 $(x,y)$"的 $O(N)$ 技巧；D 是"按比例分组 + 事件扫描容斥"；E 是经典的"线段不交 $\Leftrightarrow$ LIS"转化；F 考察对"峰/谷"结构的洞察力并转化为组合计数，较有区分度；G 是全场最难的压轴题，需要掌握 Power Projection（幂投影）与形式幂级数（FPS），涉及 NTT 等大量前置知识。其中 F 题官方未提供题解，下面给出的是根据题意自行推导的解法。

---

A - 2^n - 2*n

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_a

题目大意

给定整数 $N$（$1 \le N \le 11$），输出 $2^N - 2N$ 的值。

思路

这是纯粹的数值计算题，没有任何陷阱。直接计算 $2^N$ 与 $2N$ 并相减即可。

计算 $2^N$ 有若干种方式：

• 用 for 循环乘 $N$ 次；
• 用快速幂；
• 直接用位运算 1 << N（因为 $1 \ll N = 2^N$）；
• 或用内置 pow（注意对整数用 pow 会返回 double，可能产生精度问题，本题范围很小不会有问题，但推荐避免）。

由于 $N \le 11$，$2^N \le 2048$，用 int 就足够，不会溢出。容易验证 $N=11$ 时 $2^{11}-2\times 11 = 2048-22 = 2026$，与标题呼应。

易错点：注意运算优先级，位运算 << 的优先级低于 - 与 *，因此要写成 (1 << n) - 2 * n。

参考代码

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

int main() {
    int n;
    cin >> n;
    cout << (1 << n) - 2 * n << "\n";
    return 0;
}

官方题解还给出了 Python 写法（一行完成）：

n = int(input())
print(2**n - 2*n)

复杂度分析

• 时间复杂度：$O(1)$（位运算）或 $O(N)$（循环累乘），均远小于限制。
• 空间复杂度：$O(1)$。

---

B - Happy Number

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_b

题目大意

给定正整数 $N$（$1 \le N \le 2026$），判断它是否为"快乐数"：反复执行"把数替换为其十进制各位数字的平方和"这一操作，若经过有限次操作后能变成 $1$，则输出 Yes，否则输出 No。

思路

关键观察 1：设 $f(n)=\sum d^2$（$d$ 遍历 $n$ 的十进制位）。若从 $N$ 开始反复应用 $f$ 过程中再次碰到一个已经出现过的数（且未到达 $1$），那么之后会永远在这个环上循环，不可能到达 $1$。因此可以用一个 set 记录访问历史：

• 只要 $n \neq 1$，就判断 $n$ 是否访问过：若访问过则输出 No；否则记录并把 $n$ 替换为 $f(n)$；
• 循环正常退出（$n=1$）则输出 Yes。

关键观察 2（迭代次数上界）：因为 $N \le 2026$ 至多 4 位，所以 $f(N) \le 9^2\times 4 = 324$；再应用一次则 $f(f(N)) \le 9^2\times 3 = 243$。之后所有不超过 $243$ 的数的函数值仍不超过 $243$（$f$ 不增：对任意 $y \le 243$，$f(y) \le 9^2 \times 3 = 243$）。因此迭代值被"困"在 $[1,243]$ 内，最多迭代约 $300$ 次必然出现重复或到达 $1$。所以上面的 set 判重写法必然快速终止。

易错点：经典快乐数序列 $439 \to 106 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to \dots$ 会进入不含 $1$ 的环，必须正确识别为 No；而不要只循环固定次数就武断下结论（虽然固定迭代约 $300$ 次再判断也可行，但判重写法更稳妥）。

参考代码

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

int f(int n) {
    int res = 0;
    while (n) {
        int d = n % 10;
        res += d * d;
        n /= 10;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    set<int> seen;
    while (n > 1) {
        if (seen.count(n)) {
            cout << "No\n";
            return 0;
        }
        seen.insert(n);
        n = f(n);
    }
    cout << "Yes\n";
    return 0;
}

复杂度分析

• 时间复杂度：迭代次数不超过约 $300$，每次求 $f$ 至多 4 位，可视为 $O(1)$。
• 空间复杂度：$O(1)$（记录访问过的数不超过约 $300$ 个）。

---

C - 2026

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_c

题目大意

正整数 $n$ 称为好整数，当且仅当恰好存在一对整数 $(x,y)$ 满足 $0 < x < y$ 且 $x^2 + y^2 = n$。给定 $N$（$1 \le N \le 10^7$），输出所有不超过 $N$ 的好整数：第一行为个数 $k$，第二行为升序排列的 $k$ 个数（若 $k=0$，第二行为空行）。

思路

先想朴素的错误做法：对每个 $n$（$1 \le n \le N$）枚举 $x$（$1 \le x \le \sqrt n$），计算 $y=\sqrt{n-x^2}$ 判断是否为整数且 $x<y$，统计满足条件的 $(x,y)$ 对数是否为 1。这样做的时间为 $O(N\sqrt N)$，对 $N=10^7$ 完全不可行。

关键转化：反过来枚举 $(x,y)$。既然 $x^2+y^2 \le N$，那么 $x, y \le \sqrt N \approx 3163$。不妨直接枚举所有满足 $x^2+y^2 \le N$ 且 $0<x<y$ 的整数对 $(x,y)$，用一个计数数组 $c$ 记录每个 $n=x^2+y^2$ 被覆盖的次数：

$$c_{x^2+y^2} \mathrel{+}= 1.$$

最后满足 $c_n = 1$ 的 $n$ 就是好整数（恰好被一对 $(x,y)$ 表示）。

为什么复杂度是 $O(N)$：满足 $x^2+y^2 \le N$ 的格点 $(x,y)$（$x,y>0$）数量大约是第一象限内半径 $\sqrt N$ 的四分之一圆面积，即 $\dfrac{\pi}{4}N = O(N)$。枚举时以 $x$ 为外层循环、$y>x$ 为内层循环，并且在内层当 $x^2+y^2>N$ 时及时 break。

边界与易错点：

• 要求 $0<x<y$，所以 $y$ 从 $x+1$ 开始，恰好覆盖每一对无序对一次（不会重复计数，也不会把 $(x,y)$ 与 $(y,x)$ 算两次）。
• 题目要求"恰好一对"，所以输出 $c_n=1$ 的 $n$，而不是 $c_n \ge 1$。
• 输出格式：$k=0$ 时第二行输出空行（上面代码在 ans 为空时只输出第一行的 0，符合要求）。

参考代码

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

int main() {
    int N;
    cin >> N;
    vector<int> c(N + 1, 0);
    for (int x = 1; x * x <= N; x++) {
        for (int y = x + 1; x * x + y * y <= N; y++) {
            c[x * x + y * y]++;
        }
    }
    vector<int> ans;
    for (int n = 1; n <= N; n++) {
        if (c[n] == 1) ans.push_back(n);
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i] << (i + 1 == (int)ans.size() ? "\n" : " ");
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$（枚举的 $(x,y)$ 对数约为 $\frac{\pi}{4}N$）。
• 空间复杂度：$O(N)$（计数数组）。

---

D - Kadomatsu Subsequence

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_d

题目大意

给定长度 $N$（$1 \le N \le 3\times 10^5$）的整数序列 $A$。求满足以下条件的三元组 $(i,j,k)$ 的个数：

• $1 \le i,j,k \le N$；
• $A_i : A_j : A_k = 7:5:3$；
• $\min(i,j,k) = j$ 或 $\max(i,j,k) = j$。

思路

关键观察 1：按比例分组。因为 $A$ 中元素都是正整数，$A_i:A_j:A_k = 7:5:3$ 等价于存在正整数 $t$ 使得

$$A_i = 7t,\quad A_j = 5t,\quad A_k = 3t.$$

由于 $7t \neq 5t \neq 3t$，三个元素值两两不同，因此 $i,j,k$ 三个下标也必然两两不同。对每个 $t$，分别收集值为 $7t$、$5t$、$3t$ 的下标集合 $V_7,V_5,V_3$。忽略下标条件时，贡献为

$$|V_7|\cdot|V_5|\cdot|V_3|.$$

关键观察 2：处理下标条件。条件"$\min(i,j,k)=j$ 或 $\max(i,j,k)=j$"意味着 $j$ 是三者的下标中最小或最大，也就是 $j$ 不可能是三者的中间下标。由于 $i,j,k$ 两两不同，被排除的只是 $i<j<k$ 与 $k<j<i$ 两类。

于是对每个 $t$：先按全部计数 $|V_7|\cdot|V_5|\cdot|V_3|$，再减去"$j$ 在中间"的个数。

如何统计"$j$ 在中间"：把 $V_7,V_5,V_3$ 中的下标合并后按下标升序扫描，同时维护：

• $p_7$：已经扫描过的 $7t$ 下标个数；$s_7$：尚未扫描的 $7t$ 下标个数；
• $p_3$：已经扫描过的 $3t$ 下标个数；$s_3$：尚未扫描的 $3t$ 下标个数。

当遇到一个 $5t$ 下标 $j$ 时：

• $i<j<k$ 的情形数为 $p_7 \times s_3$（$i$ 是已扫过的 $7t$ 下标、$k$ 是未扫过的 $3t$ 下标）；
• $k<j<i$ 的情形数为 $p_3 \times s_7$。

把这两者从总数中减去即可。

正确性：每个"$j$ 在中间"的三元组恰好在扫描到该 $j$ 时被减去一次；不在中间的不会被减。对所有 $t$ 求和即为答案。

易错点：

• 答案上限约为 $N^3 = 2.7\times 10^{16}$，超出 32 位整数范围，必须用 64 位整数（long long）。
• 某 $t$ 只出现在 $V_7$ 而不在 $V_5,V_3$ 时贡献为 0，可以直接跳过；用 map 按 $t$ 分组即可。

参考代码

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

// 对单个 t 计算：总数减去 "j 在下标中间" 的个数
ll solve_group(vector<ll>& v7, vector<ll>& v5, vector<ll>& v3) {
    ll res = (ll)v7.size() * v5.size() * v3.size();
    if (res == 0) return 0;

    vector<pair<ll, int>> vp;   // (下标, 类型)：7 / 5 / 3
    for (auto x : v7) vp.push_back({x, 7});
    for (auto x : v5) vp.push_back({x, 5});
    for (auto x : v3) vp.push_back({x, 3});
    sort(vp.begin(), vp.end());

    ll p7 = 0, s7 = v7.size();
    ll p3 = 0, s3 = v3.size();
    for (auto& pr : vp) {
        if (pr.second == 7) { p7++; s7--; }
        else if (pr.second == 5) {
            res -= p7 * s3;   // i < j < k
            res -= p3 * s7;   // k < j < i
        } else { p3++; s3--; }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    map<pair<ll, int>, vector<ll>> mp;
    set<ll> tst;
    for (ll i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (a % 7 == 0) { mp[{a / 7, 7}].push_back(i); tst.insert(a / 7); }
        if (a % 5 == 0) mp[{a / 5, 5}].push_back(i);
        if (a % 3 == 0) mp[{a / 3, 3}].push_back(i);
    }
    ll ans = 0;
    for (auto t : tst) {
        ans += solve_group(mp[{t, 7}], mp[{t, 5}], mp[{t, 3}]);
    }
    cout << ans << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N)$（按 $t$ 分组用 map，每组内排序扫描）。
• 空间复杂度：$O(N)$。

---

E - Kite

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_e

题目大意

$N$（$1 \le N \le 2\times 10^5$）个人站在河边，第 $i$ 个人站在 $(A_i,0)$，风筝在 $(B_i,1)$。若两条"$(A_i,0)-(B_i,1)$"线段相交（含端点相触），则两人不能同时放风筝。求能同时放风筝的最大人数。

思路

关键观察 1：两条线段何时相交？ 线段 $i$ 在高度 $y \in [0,1]$ 处的横坐标为 $A_i + (B_i-A_i)y$（线性插值）。两条线段相交当且仅当存在 $y\in[0,1]$ 使得

$$A_i + (B_i-A_i)y = A_j + (B_j-A_j)y,$$

即 $A_i-A_j$ 与 $B_i-B_j$ 异号（或其一为 0）。因此两人可以同时放风筝当且仅当

$$A_i < A_j \text{ 且 } B_i < B_j,\qquad \text{或}\qquad A_i > A_j \text{ 且 } B_i > B_j,$$

即点对 $(A_i,B_i)$ 与 $(A_j,B_j)$ 严格同序。这也对应线段整体上"一条始终在另一条上方"而不交叉。

关键观察 2：转化为 LIS。把所有人按 $A$ 升序排列，问题变成：选取尽可能多的点，使得任意两点的 $B$ 也严格递增——这正是对 $B$ 序列求最长上升子序列（LIS）。

关于 $A$ 相同的平局处理：若两人 $A$ 相等，则起点相同，线段在端点 $(A,0)$ 处相触，属于"不能同时"（题目明确包含端点相触）。在排序时按 $A$ 升序、$A$ 相同时按 $B$ 降序 排列，这样 $A$ 相同的点在 $B$ 序列里是严格递减的，LIS（严格递增）不可能同时选到它们，从而自动规避了冲突。

LIS 的 $O(N\log N)$ 求法：维护数组 dp，dp[i] 表示长度为 $i+1$ 的上升子序列的最小末尾值；对每个 $B$，用 lower_bound 找到第一个不小于它的位置并替换，dp 的长度即为 LIS 长度。

易错点：平局排序方向必须与 LIS 的方向配合——由于我们要求严格递增，$A$ 相同必须降序排 $B$；若误升序排则会错误地允许 $A$ 相同的两人同时入选。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<pair<int, int>> AB(N);
    for (auto& [a, b] : AB) cin >> a >> b;

    // A 升序；A 相同时 B 降序（防止同 A 的两点同时入选）
    sort(AB.begin(), AB.end(), [](auto& l, auto& r) {
        if (l.first == r.first) return l.second > r.second;
        return l.first < r.first;
    });

    vector<int> dp;
    for (auto& [a, b] : AB) {
        int i = lower_bound(dp.begin(), dp.end(), b) - dp.begin();
        if (i == (int)dp.size()) dp.push_back(b);
        else dp[i] = b;
    }
    cout << dp.size() << "\n";
    return 0;
}

复杂度分析

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

---

F - Beautiful Kadomatsu

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_f

（本题暂无官方题解，以下为根据题意推导的解法。）

题目大意

长度为 $k$ 的序列 $a=(a_1,\dots,a_k)$ 称为 kadomatsu-like，当且仅当其"峰数"严格大于"谷数"，其中：

• 峰：满足 $a_{i-1} < a_i$ 且 $a_i > a_{i+1}$ 的 $i$（$2\le i\le k-1$）的个数，记为 $x$；
• 谷：满足 $a_{i-1} > a_i$ 且 $a_i < a_{i+1}$ 的 $i$ 的个数，记为 $y$；

要求 $x>y$。给定 $1..N$ 的一个排列 $P$（$1\le N\le 3\times 10^5$），求 $P$ 的子序列（不必连续）中是 kadomatsu-like 的个数，对 $998244353$ 取模。

思路

Step 1：把"峰多于谷"转化为"首升尾降"。

设子序列相邻元素的差符号序列为 $s_i=\operatorname{sgn}(a_i-a_{i-1})$（$i=2,\dots,k$）。于是：

• 峰 $x$ = 符号对 $(+,-)$ 的出现次数（先升后降）；
• 谷 $y$ = 符号对 $(-,+)$ 的出现次数。

把符号序列中连续的相同符号合并成一段，得到一个严格交替的符号段序列。任意两个相邻符号段之间恰好发生一次 $(+,-)$ 或 $(-,+)$ 的转变，且转变类型必然交替出现（$(+,-)\to(-,+)\to(+,-)\to\cdots$）。因此 $x$ 与 $y$ 之差至多为 1。具体地：

• 符号段首为 $+$、尾为 $-：$ 转变序列为 $+,-,+,-,\dots,+,-$，故 $x=y+1$；
• 首为 $+$、尾为 $+：$ $x=y$；
• 首为 $-$、尾为 $-：$ $x=y$；
• 首为 $-$、尾为 $+：$ $y=x+1$。

所以

$$x>y \iff \text{符号段首为 }+ \text{ 且尾为 }- \iff a_1<a_2 \ \text{且}\ a_{k-1}>a_k.$$

即一个子序列是 kadomatsu-like 当且仅当它的第一步上升、最后一步下降。注意长度为 1 或 2 的子序列不可能同时满足这两个条件（$k=2$ 时要求 $a_1<a_2$ 又要求 $a_1>a_2$，矛盾），自动被排除。

Step 2：组合计数。

合法子序列由三部分组成：

1. 上升边：首两个元素 $(i_1,i_2)$，满足 $i_1<i_2$ 且 $P_{i_1}<P_{i_2}$；
2. 中间部分：下标严格介于 $i_2$ 与 $i_{k-1}$ 之间的任意子集（可为空）；
3. 下降边：末两个元素 $(i_{k-1},i_k)$，满足 $i_{k-1}<i_k$ 且 $P_{i_{k-1}}>P_{i_k}$。

上升边、下降边、中间子集三者唯一决定一个合法子序列，且无重复计数。

固定上升边 $(a,b)$ 与下降边 $(c,d)$（需 $b\le c$），中间有 $c-b-1$ 个位置可以任意选入子序列，方案数为 $2^{c-b-1}$（当 $c=b$ 时中间为空，方案数为 1）。因此

$$\text{Ans}=\sum_{\substack{b\le c\\\text{上升边}(a,b),\ \text{下降边}(c,d)}} 2^{\max(0,\,c-b-1)}.$$

Step 3：用前缀/后缀信息 $O(N\log N)$ 计算。

定义（以下下标按 0 起始）：

$$U_b=\#\{a<b:\ P_a<P_b\}\qquad(\text{以 }b\text{ 为终点的上升边数}),$$

$$D_c=\#\{d>c:\ P_c>P_d\}\qquad(\text{以 }c\text{ 为起点的下降边数}).$$

把和式按 $c$ 与 $b$ 的关系拆分：

• $c=b$ 的情形：贡献 $\sum_b U_bD_b$；
• $c>b$ 的情形：上升边 $(a,b)$ 有 $U_b$ 条、下降边 $(c,d)$ 有 $D_c$ 条，中间权重 $2^{c-b-1}$，故贡献

$$\sum_b U_b\sum_{c>b} D_c\,2^{c-b-1}=\sum_b U_b\cdot 2^{-(b+1)}\cdot \underbrace{\sum_{c>b}D_c\,2^c}_{=:S_b}.$$

综合得到

$$\text{Ans}=\sum_b U_bD_b+\sum_b U_b\,2^{-(b+1)}\,S_b,\qquad S_b=\sum_{c>b}D_c\,2^c.$$

$U_b$ 可用树状数组从左到右扫描求出（查询小于 $P_b$ 的前缀元素个数）；$D_c$ 用树状数组从右到左扫描求出；$S_b$ 是 $D_c\cdot 2^c$ 的后缀和，直接 $O(N)$ 递推。所有运算在模 $998244353$ 下进行，$2^{-(b+1)}$ 用 2 的逆元（$\frac{MOD+1}{2}$）的幂次表示。

正确性小结：Step 1 证明了"峰>谷"与"首升尾降"等价；Step 2 把计数分解为不重复的（上升边, 中间子集, 下降边）三元组；Step 3 用树状数组与后缀和把暴力枚举压缩到 $O(N\log N)$。

易错点：指数 $c-b-1$ 在 $c=b$ 时对应的是"空中间"，应取权重 1，因此用 $c=b$ 单独求和、$c>b$ 时用 $2^{c-b-1}$ 的拆分方式（$2^{-(b+1)}$ 与 $2^c$ 的乘积）避免出现 $2^{-1}$。实测对全部样例与随机暴力对拍均一致。

参考代码

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n) : n(n), bit(n + 1, 0) {}
    void add(int i, int v) { for (; i <= n; i += i & -i) bit[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> P(N);
    for (int& x : P) cin >> x;

    ll inv2 = (MOD + 1) / 2;
    vector<ll> pow2(N + 2), inv2p(N + 2);
    pow2[0] = inv2p[0] = 1;
    for (int i = 1; i <= N + 1; i++) {
        pow2[i] = pow2[i - 1] * 2 % MOD;
        inv2p[i] = inv2p[i - 1] * inv2 % MOD;
    }

    vector<ll> U(N), D(N);
    {   // U[b] = #{a < b : P[a] < P[b]}
        BIT bit(N);
        for (int b = 0; b < N; b++) {
            U[b] = bit.sum(P[b] - 1);
            bit.add(P[b], 1);
        }
    }
    {   // D[c] = #{d > c : P[c] > P[d]}
        BIT bit(N);
        for (int c = N - 1; c >= 0; c--) {
            D[c] = bit.sum(P[c] - 1);
            bit.add(P[c], 1);
        }
    }

    // suff[b] = sum_{c > b} D[c] * 2^c
    vector<ll> suff(N + 1, 0);
    for (int c = N - 1; c >= 0; c--) {
        suff[c] = (suff[c + 1] + D[c] * pow2[c]) % MOD;
    }

    ll term1 = 0, term2 = 0;
    for (int b = 0; b < N; b++) {
        term1 = (term1 + U[b] * D[b]) % MOD;              // c = b
        term2 = (term2 + U[b] * inv2p[b + 1] % MOD * suff[b + 1]) % MOD;  // c > b
    }
    cout << (term1 + term2) % MOD << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N)$（两个树状数组）。
• 空间复杂度：$O(N)$。

---

G - Sugoroku 6

题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_g

题目大意

有编号 $0,1,\dots,N$ 的 $N+1$ 个格子（$1\le N\le 2.5\times 10^5$）和一个 $M$ 面骰子，各面为两两不同的正整数 $A_1<\dots<A_M$（$1\le A_i\le N$），掷出各面的概率均为 $1/M$。$L$（$2\le L\le 2.5\times 10^5$）个人的棋子最初都在格子 $0$，按 $1,2,\dots,L,1,2,\dots$ 轮流掷骰：掷出 $y$ 时棋子从 $x$ 移到 $\min(N,x+y)$。第一个到达格子 $N$ 的人获胜。对每个人求其获胜概率对 $998244353$ 取模后的值。

思路

这是本场最难的题，需要 Power Projection（幂投影） 与形式幂级数（FPS）技术。整体分三步：先求单个棋子的相关概率，再套用"第 $i$ 人在第 $k$ 轮获胜"的概率公式，最后用分式合并技巧一次性求出前 $L-1$ 个人的答案。

Step 1：单个棋子的概率生成函数。

定义：

• $f_n$：单个棋子操作 $n$ 次后仍未到达格子 $N$ 的概率；
• $g_n$：单个棋子恰好第 $n$ 次操作到达格子 $N$ 的概率。

由于棋子位置单调不减，到达 $N$ 后不会再变，因此

$$g_n=f_{n-1}-f_n\quad(n\ge 1),\qquad f_n=0\ (n\ge N).$$

（每次至少前进 1 格，$N$ 次内必然到达 $N$。）

令 $D(x)$ 为一次掷骰子前进格数的概率生成函数：

$$D(x)=\frac{1}{M}\sum_{i=1}^{M}x^{A_i}.$$

那么掷 $n$ 次后棋子位于格子 $k$ 的概率为 $[x^k]D(x)^n$（前进格数之和恰好为 $k$ 且 $k<N$ 时未到达终点；由于 $k\ge N$ 已被封顶，$k<N$ 正是"未到达"）。于是

$$f_n=\sum_{k=0}^{N-1}[x^k]D^n=[x^{N-1}]\bigl(1+x+\cdots+x^{N-1}\bigr)D^n.$$

记 $G(x)=1+x+\cdots+x^{N-1}$、$F(x)=D(x)$。我们需要的正是

$$f_n=[x^{N-1}]\,F(x)^n G(x)\qquad(n=0,1,\dots,N-1),$$

即形如 $[x^{N-1}]F^nG$ 的一族值——恰好是 Power Projection 的标准形式。

Step 2：Power Projection。

Power Projection 问题：给定次数为 $n$ 的多项式 $f(x),g(x)$，求 $h_i=[x^n]f(x)^ig(x)$（$i=0,\dots,n$）。利用

$$\sum_{i\ge 0} y^i f(x)^i g(x)=\frac{g(x)}{1-y\,f(x)},$$

$h_i$ 正是双变量形式幂级数 $\dfrac{g(x)}{1-yf(x)}$ 中 $[x^n y^i]$ 的系数。当 $[x^0]f=0$ 时（本题 $D(x)$ 无常数项，满足），可以用 Bostan–Mori 算法对 $x$ 的次数做对半递推，同时 $y$ 的次数翻倍：

$$\frac{P(x,y)}{Q(x,y)}\ \xrightarrow{\text{令 }R(x,y)=Q(-x,y)}\ \frac{P R}{Q R}=\frac{S}{T},$$

其中 $T$ 只含 $x$ 的偶次项，于是 $[x^n]\frac{P}{Q}=[x^{\lfloor n/2\rfloor}]\frac{S^{(n\bmod 2)}}{T^{(2)}}$，$x$ 的次数每次减半。每轮 $x$ 次数 $\lfloor n/2^t\rfloor$、$y$ 次数 $2^t$，用分块填充把双变量乘法变成一维卷积 + NTT，每轮 $O(n\log n)$，共 $O(\log n)$ 轮，总复杂度 $O(n\log^2 n)$。最后 $x$ 次数变为 0，返回 $P_0(y)\cdot Q_0(y)^{-1}$ 的系数即可。

Step 3：把 $f_n$ 组装成每个人的获胜概率。

第 $i$ 个人在自己的第 $k$ 次掷骰时获胜，要求：

• 前 $i-1$ 个人在各自的前 $k$ 次掷骰内均未到达 $N$：概率 $f_k^{\,i-1}$；
• 后 $L-i$ 个人在各自的前 $k-1$ 次掷骰内均未到达 $N$：概率 $f_{k-1}^{\,L-i}$；
• 第 $i$ 个人恰好第 $k$ 次到达：概率 $g_k$。

三件事互相独立，故第 $i$ 人的胜率为

$$\text{Ans}_i=\sum_{k=1}^{N} g_k\, f_k^{\,i-1}\, f_{k-1}^{\,L-i}.$$

对 $i=L$：$f_{k-1}^{\,0}=1$，可直接 $O(N)$ 求和

$$\text{Ans}_L=\sum_{k=1}^{N} g_k\, f_k^{\,L-1}.$$

对 $1\le i<L$：若 $f_{k-1}=0$，该项为 $0$ 可忽略；否则令 $r_k=f_k/f_{k-1}$，则

$$g_k f_k^{\,i-1}f_{k-1}^{\,L-i}=g_k f_{k-1}^{\,L-1}\Bigl(\frac{f_k}{f_{k-1}}\Bigr)^{i-1}=[y^{i-1}]\frac{g_k\,f_{k-1}^{\,L-1}}{1-r_k y}.$$

于是

$$\text{Ans}_i=[y^{i-1}]\sum_{1\le k\le N,\ f_{k-1}\neq 0}\frac{g_k\,f_{k-1}^{\,L-1}}{1-r_k y}\qquad(1\le i<L).$$

这是 $N$ 个"一次分式"的和。用分治/线段树合并：每个分式是 $(n_k,d_k)=\bigl(g_k f_{k-1}^{L-1},\ 1-r_k y\bigr)$，两两合并

$$\frac{n_1}{d_1}+\frac{n_2}{d_2}=\frac{n_1d_2+n_2d_1}{d_1d_2},$$

所有多项式只保留前 $L$ 个系数（模 $y^L$），合并过程总代价 $O(N\log^2 N)$。最终得到 $S(y)=\dfrac{N(y)}{D(y)}$，用多项式求逆求出 $D(y)^{-1}\bmod y^L$ 后与 $N(y)$ 相乘，$[y^{i-1}]$ 即 $\text{Ans}_i$。总复杂度 $O(N\log^2 N+L\log L)$。

易错点与边界：

• 所有概率均在模 $998244353$ 下计算，掷骰概率为 $M^{-1}$。
• $A_i=N$ 的面在 $[x^{N-1}]D^nG$ 中不会贡献（涉及它的项次数至少 $N$），可安全地忽略，代码中 if (a < N) 即为此。
• 第 $k=N$ 项：对 $i\ge 2$ 有 $f_N^{i-1}=0$；对 $i=1$ 需要保留 $k=N$ 项（其 $r_N=0$，恰为常数项 $f_{N-1}^L$），因此分式合并需要遍历 $k=1..N$ 而非 $k=1..N-1$；$\text{Ans}_L$ 的求和里 $k=N$ 项为 $g_Nf_N^{L-1}=0$，遍历 $k=1..N-1$ 即可。
• 该解法的参考实现是"教学级"的（为便于理解未做极限常数优化）；在正式评测环境下可用 AtCoder Library（ACL）的 convolution/formal_power_series 提速。

参考代码

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

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

void ntt(vector<int>& 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) {
        int 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++) {
                int u = a[i + j];
                int v = (int)((ll)a[i + j + len / 2] * w % MOD);
                int x = u + v; if (x >= MOD) x -= MOD;
                int y = u - v; if (y < 0) y += MOD;
                a[i + j] = x;
                a[i + j + len / 2] = y;
                w = w * wlen % MOD;
            }
        }
    }
    if (invert) {
        int inv_n = modpow(n, MOD - 2);
        for (int& x : a) x = (int)((ll)x * inv_n % MOD);
    }
}

vector<int> convolution(const vector<int>& a, const vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    int need = (int)a.size() + (int)b.size() - 1;
    if (min((int)a.size(), (int)b.size()) <= 60) {      // 小规模直接暴力
        vector<int> res(need);
        for (int i = 0; i < (int)a.size(); i++)
            for (int j = 0; j < (int)b.size(); j++)
                res[i + j] = (res[i + j] + (ll)a[i] * b[j]) % MOD;
        return res;
    }
    int n = 1;
    while (n < need) n <<= 1;
    vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n); fb.resize(n);
    ntt(fa, false); ntt(fb, false);
    for (int i = 0; i < n; i++) fa[i] = (ll)fa[i] * fb[i] % MOD;
    ntt(fa, true);
    fa.resize(need);
    return fa;
}

// 多项式求逆：a[0] != 0，求 a 的逆模 x^n
vector<int> fps_inv(const vector<int>& a, int n) {
    vector<int> r(1, modpow(a[0], MOD - 2));
    int m = 1;
    while (m < n) {
        m <<= 1;
        vector<int> f(a.begin(), a.begin() + min((int)a.size(), m));
        f.resize(m);
        auto t = convolution(f, r);
        t.resize(m);
        for (int& x : t) x = x ? MOD - x : 0;
        t[0] += 2; if (t[0] >= MOD) t[0] -= MOD;
        r = convolution(r, t);
        r.resize(m);
    }
    r.resize(n);
    return r;
}

int npow2(int x) {
    int r = 1;
    while (r < x) r <<= 1;
    return r;
}

// 幂投影：返回 pp[i] = [x^{n}] f(x)^i g(x)（i = 0..n，n = f.size()-1，要求 [x^0] f = 0）
vector<int> power_projection(const vector<int>& f, const vector<int>& g) {
    int n = (int)f.size() - 1;
    int n0 = n;
    int k = 1;                       // 当前 y 的次数
    int K = npow2(2 * k + 1);        // 分块大小，避免 y 方向进位
    vector<int> P((n + 1) * K, 0), Q((n + 1) * K, 0);
    for (int i = 0; i <= n; i++) {
        P[i * K] = g[i];
        Q[i * K + 1] = f[i] ? MOD - f[i] : 0;
    }
    Q[0] = 1;                        // Q(x,y) = 1 - y f(x)
    while (n > 0) {
        vector<int> R = Q;           // R(x,y) = Q(-x,y)
        for (int i = 1; i <= n; i += 2)
            for (int j = 0; j <= k; j++) {
                int& x = R[i * K + j];
                x = x ? MOD - x : 0;
            }
        int len = (n + 1) * K;
        int need = 2 * len - 1;
        int sz = 1;
        while (sz < need) sz <<= 1;
        vector<int> a(P.begin(), P.begin() + len);
        vector<int> b(R.begin(), R.begin() + len);
        vector<int> q(Q.begin(), Q.begin() + len);
        a.resize(sz); b.resize(sz); q.resize(sz);
        ntt(a, false); ntt(b, false); ntt(q, false);
        for (int i = 0; i < sz; i++) {
            a[i] = (ll)a[i] * b[i] % MOD;   // S = P * R
            q[i] = (ll)q[i] * b[i] % MOD;   // T = Q * R
        }
        ntt(a, true); ntt(q, true);
        a.resize(need); q.resize(need);

        int n2 = n / 2, k2 = 2 * k;
        int K2 = npow2(2 * k2 + 1);
        vector<int> U((n2 + 1) * K2, 0), V((n2 + 1) * K2, 0);
        int parity = n & 1;
        for (int i = 0; i <= n2; i++) {
            int rowS = 2 * i + parity;
            int rowT = 2 * i;
            for (int j = 0; j <= k2; j++) {
                U[i * K2 + j] = a[rowS * K + j];
                V[i * K2 + j] = q[rowT * K + j];
            }
        }
        P = move(U);
        Q = move(V);
        n = n2;
        k = k2;
        K = K2;
    }
    vector<int> num(k + 1), den(k + 1);
    for (int j = 0; j <= k; j++) {
        num[j] = P[j];
        den[j] = Q[j];
    }
    auto den_inv = fps_inv(den, n0 + 1);
    auto res = convolution(num, den_inv);
    res.resize(n0 + 1);
    return res;
}

// 合并两个一次分式：(n1,d1) + (n2,d2) = (n1*d2 + n2*d1, d1*d2)，只保留前 T 个系数
pair<vector<int>, vector<int>> merge_frac(const vector<int>& n1, const vector<int>& d1,
                                          const vector<int>& n2, const vector<int>& d2, int T) {
    auto a = convolution(n1, d2);
    auto b = convolution(n2, d1);
    vector<int> num(T, 0), den(T, 0);
    for (int i = 0; i < T; i++) {
        int x = i < (int)a.size() ? a[i] : 0;
        int y = i < (int)b.size() ? b[i] : 0;
        int s = x + y; if (s >= MOD) s -= MOD;
        num[i] = s;
    }
    auto d = convolution(d1, d2);
    for (int i = 0; i < T; i++) den[i] = i < (int)d.size() ? d[i] : 0;
    return {num, den};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, L;
    cin >> N >> M >> L;
    vector<int> A(M);
    for (auto& x : A) cin >> x;

    int invM = modpow(M, MOD - 2);
    vector<int> D(N, 0);                       // D(x) = (1/M) sum x^{A_i}，次数 0..N-1
    for (auto a : A) {
        if (a < N) {                            // 次数 >= N 的项不影响 [x^{N-1}]
            D[a] += invM; if (D[a] >= MOD) D[a] -= MOD;
        }
    }
    vector<int> G(N, 1);                        // 1 + x + ... + x^{N-1}

    auto f = power_projection(D, G);            // f[i] = f_i（i = 0..N-1）
    f.resize(N + 1);
    f[N] = 0;                                   // f_N = 0

    vector<int> g(N + 1);                       // g[k] = f[k-1] - f[k]，k = 1..N
    for (int k = 1; k <= N - 1; k++) {
        int x = f[k - 1] - f[k]; if (x < 0) x += MOD;
        g[k] = x;
    }
    g[N] = f[N - 1];

    // 前 L-1 个人：分式之和 S(y) = sum_k (g_k f_{k-1}^{L-1}) / (1 - r_k y)
    int T = L;
    vector<pair<vector<int>, vector<int>>> fracs;
    for (int k = 1; k <= N; k++) {
        if (f[k - 1] == 0) continue;
        int fkm1 = f[k - 1];
        int num0 = (ll)g[k] * modpow(fkm1, L - 1) % MOD;
        int rk = (ll)f[k] * modpow(fkm1, MOD - 2) % MOD;
        vector<int> num(1, num0);
        vector<int> den = {1, rk ? MOD - rk : 0};
        fracs.push_back({num, den});
    }
    while (fracs.size() > 1) {                  // 分治合并所有分式
        vector<pair<vector<int>, vector<int>>> nxt;
        for (int i = 0; i + 1 < (int)fracs.size(); i += 2) {
            nxt.push_back(merge_frac(fracs[i].first, fracs[i].second,
                                     fracs[i + 1].first, fracs[i + 1].second, T));
        }
        if (fracs.size() % 2 == 1) nxt.push_back(fracs.back());
        fracs = move(nxt);
    }

    vector<int> ans(L + 1, 0);
    if (!fracs.empty()) {
        auto& num = fracs[0].first;
        auto& den = fracs[0].second;
        auto den_inv = fps_inv(den, T);
        auto coeff = convolution(num, den_inv);
        for (int i = 1; i <= L - 1; i++) {
            if (i - 1 < (int)coeff.size()) ans[i] = coeff[i - 1];
        }
    }
    // 第 L 个人：ans[L] = sum_k g_k f_k^{L-1}（k=N 的项为 0，不必枚举）
    int sumL = 0;
    for (int k = 1; k <= N - 1; k++) {
        sumL = (sumL + (ll)g[k] * modpow(f[k], L - 1)) % MOD;
    }
    ans[L] = sumL;

    for (int i = 1; i <= L; i++) cout << ans[i] << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\log^2 N + L\log L)$（Power Projection 每轮 $O(N\log N)$ 共 $O(\log N)$ 轮；分式合并 $O(N\log^2 N)$；末尾多项式求逆与乘法 $O(L\log L)$）。
• 空间复杂度：$O(N+L)$。