AtCoder Beginner Contest 436 题解

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

比赛概览

本场整体难度适中，前四题偏基础：A 是字符串补齐，B 是经典的奇数阶幻方模拟，C 的 $N$ 高达 $10^9$，考察"两个 $2\times 2$ 方块重叠 $\iff$ 左上角坐标差均不超过 1"这一关键观察，用集合维护即可；D 是带传送格的网格 BFS，关键优化是每种字母只展开一次传送。后半场拉开差距：E 需要把最小交换次数与置换的环数联系起来（$K=N-C$），F 用 Fenwick 树统计，核心是把"最暗星星为 $i$ 的集合数"转化为"左右两侧更亮星星数量"的组合计数；G 是一道较难的计数题，需要借助"把 $M$ 反复减半"的系数向量技巧，并用卷积（NTT）加速，值得重点掌握。

---

A - o-padding

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_a

题目大意

输入整数 $N$（$2\le N\le 100$）和仅由小写字母组成的字符串 $S$（长度 $1\le |S|\le N-1$）。输出在 $S$ 的开头不断添加字符 o、直至长度恰好为 $N$ 后得到的字符串。

思路

目标长度是 $N$，$S$ 已经有 $|S|$ 个字符，所以只需在 $S$ 前面补上 $N-|S|$ 个 o。这是纯粹的字符串构造，实现方式有两种：

1. 用循环输出 $N-|S|$ 次 o，再输出 $S$；
2. 用字符串构造函数 string(n - (int)s.size(), 'o') 直接生成补全部分，再与 $S$ 拼接。

一个实现细节：s.size() 的类型是 size_t（无符号），与 int 做减法时最好先显式转成 int，避免类型混用。本题保证 $N>|S|$，所以不会出现负数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    cout << string(n - (int)s.size(), 'o') << s << '\n';
    return 0;
}

官方题解同时给出了 Python 写法，一并列出：

n = int(input())
s = input()
t = 'o' * (n - len(s))
print(t + s)

复杂度分析

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

---

B - Magic Square

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_b

题目大意

输入奇数 $N$（$3\le N\le 99$）。在一个 $N\times N$ 的空网格中按如下规则填数：

1. 在 $(0,\frac{N-1}{2})$ 填 $1$；
2. 重复 $N^2-1$ 次：设上次填数的格子为 $(r,c)$、所填数为 $k$。若格子 $((r-1)\bmod N,\,(c+1)\bmod N)$ 为空，则在其中填 $k+1$；否则在 $((r+1)\bmod N,\,c)$ 填 $k+1$。

输出最终填好的 $N$ 行网格。可以证明每个格子恰好被填一次。

思路

这就是经典的奇数阶幻方 Siamese 构造法，按题意直接模拟即可。

• 用二维数组 a 存结果，初始全部为 0，用 0 表示"空"（填入的数字从 1 开始，不会与空标记冲突）。
• 维护当前位置 $(r,c)$。每次先计算候选位置 $(nr,nc)=\big((r-1+N)\bmod N,\,(c+1)\bmod N\big)$：
  • 若 a[nr][nc] == 0，把下一个数填到 $(nr,nc)$；
  • 否则填到 $((r+1)\bmod N,\,c)$（即当前格的正下方，列不变）。
• 循环 $N^2-1$ 次，把 $1$ 到 $N^2$ 依次填入。

两个实现要点：

• 模运算处理负数：写成 (r - 1 + N) % N 可以安全地得到"上移一行"后的行号，避免直接对负数取模。
• 正确性由 Siamese 方法的性质保证：每填一个数，右上格要么为空，要么已被占用；若被占用，则当前格的正下方必为空，因此总能继续，不会发生冲突。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0));
    int r = 0, c = n / 2, x = 1;
    a[r][c] = x;
    while (x < n * n) {
        int nr = (r - 1 + n) % n, nc = (c + 1) % n;
        if (a[nr][nc] != 0) { nr = (r + 1) % n; nc = c; }
        a[nr][nc] = ++x;
        r = nr; c = nc;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << a[i][j] << (j + 1 == n ? '\n' : ' ');
        }
    }
    return 0;
}

官方题解的 Python 写法：

n = int(input())
a = [[0] * n for _ in range(n)]
r, c, x = 0, n // 2, 1
a[r][c] = x
while x < n * n:
    nr = (r - 1 + n) % n
    nc = (c + 1) % n
    if a[nr][nc] != 0:
        nr = (r + 1) % n
        nc = c
    x += 1
    a[nr][nc] = x
    r, c = nr, nc
for i in range(n):
    print(" ".join(map(str, a[i])))

复杂度分析

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

---

C - 2x2 Placing

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_c

题目大意

有一个 $N\times N$ 的网格（$N$ 可达 $10^9$）。依次执行 $M$ 次操作：第 $i$ 次尝试以 $(R_i,C_i)$ 为左上角放置一个 $2\times 2$ 方块，若该 $2\times 2$ 区域与任何已放置的方块有重叠，则什么都不做。输入 $N,M$ 和 $M$ 对 $(R_i,C_i)$，输出最终网格上的方块数量。

思路

$N$ 太大，无法对每个格子开数组模拟；注意到 $M\le 2\times 10^5$，我们只需维护"已经放置的方块"的集合。

关键观察：以 $(r_1,c_1)$、$(r_2,c_2)$ 为左上角的两个 $2\times 2$ 方块重叠，当且仅当

$$|r_1-r_2|\le 1 \quad\text{且}\quad |c_1-c_2|\le 1.$$

理由：一个 $2\times 2$ 方块占据的单元格行集合为 $\{r,r+1\}$、列集合为 $\{c,c+1\}$。两方块有公共格 $\iff$ 行区间相交且列区间相交；行区间相交 $\iff |r_1-r_2|\le 1$，列区间同理。

因此，判断新方块 $(r,c)$ 是否与已有方块重叠，只需检查以 $(r,c)$ 为中心的 $3\times 3$ 邻域（$r-1\le r'\le r+1$，$c-1\le c'\le c+1$）内是否已存在方块。

实现：用 std::set<pair<int,int>>（或哈希集合）存所有已放置方块的左上角坐标。对每个询问：

1. 枚举 $r'\in\{r-1,r,r+1\}$、$c'\in\{c-1,c,c+1\}$，若集合中存在 $(r',c')$，说明会重叠；
2. 否则把 $(r,c)$ 插入集合，答案加一。

注意两点：

• 我们检查的 $3\times 3$ 邻域可能包含越界坐标（如 $0$ 或 $N$），但这些坐标永远不会出现在集合中（合法左上角只在 $1\le R_i,C_i\le N-1$ 内），所以不会误判。
• 输入中允许出现重复的 $(R_i,C_i)$（见样例 3）：第二次尝试时，$(r,c)$ 本身已在集合中，邻域检查会返回"重叠"，从而不会重复放置。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    set<pair<int,int>> st;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int r, c;
        cin >> r >> c;
        bool ok = true;
        for (int dr = -1; dr <= 1 && ok; dr++)
            for (int dc = -1; dc <= 1 && ok; dc++)
                if (st.count({r + dr, c + dc})) ok = false;
        if (ok) {
            st.insert({r, c});
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(M\log M)$（std::set 每次插入/查找 $O(\log M)$；若改用 unordered_set 则为 $O(M)$ 期望）
• 空间复杂度：$O(M)$

---

D - Teleport Maze

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_d

题目大意

输入 $H,W$（$H,W\le 1000$）和一个 $H\times W$ 的网格，其中 . 为空地、# 为障碍、小写字母为"传送格"。从 $(1,1)$ 出发，可以反复执行两种操作（代价均为 1）：

• 走路：向上下左右四邻域移动一格，不能进入障碍或越界；
• 传送：站在传送格上，移动到任意同字母的传送格。

求到 $(H,W)$ 的最少操作数；不可达输出 -1。

思路

所有边权均为 1，最短路径用普通 BFS 即可。

朴素做法的问题：若每个传送格都向所有同字母的传送格连边，那么边数会高达 $O(HW\cdot HW)$，必然超时。需要避免"重复展开"。

关键观察：设 BFS 到达了某个字母 $c$ 的传送格。如果在此之前已经到达过某个字母 $c$ 的传送格，那么从当前格出发不需要再做传送。原因是：与其从当前格传送到所有 $c$ 格，不如从那个更早到达的 $c$ 格传送——从更早的格子出发到各个 $c$ 格的距离不大于从当前格出发的距离，先到者已经把"传送到所有 $c$ 格"这一步做到最优，重复展开不可能带来更短路。

于是对每种字母，只在其第一次被访问到的那一格展开一次：把该字母的所有传送格（若未访问）入队，并打上"该字母已处理"的标记。这样所有展开的总工作量是 $O(HW)$（每个传送格至多被加入队列一次），BFS 整体就是 $O(HW)$。

实现要点：

• 预处理 pos[26]，存每种字母的所有位置；
• 用 used[26] 记录字母是否已展开；
• 起点和终点也可能是传送格，处理方式完全相同，无需特判；
• 注意：传送可以传送到当前格子自身（代价 1 的自环），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);
    vector<vector<pair<int,int>>> pos(26);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
        for (int j = 0; j < w; j++)
            if (islower((unsigned char)s[i][j]))
                pos[s[i][j] - 'a'].emplace_back(i, j);
    }
    const int INF = 1 << 30;
    vector<vector<int>> d(h, vector<int>(w, INF));
    vector<bool> used(26, false);
    queue<pair<int,int>> q;
    d[0][0] = 0;
    q.emplace(0, 0);
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
            if (s[nr][nc] == '#') continue;
            if (d[nr][nc] != INF) continue;
            d[nr][nc] = d[r][c] + 1;
            q.emplace(nr, nc);
        }
        if (islower((unsigned char)s[r][c])) {
            int ch = s[r][c] - 'a';
            if (used[ch]) continue;
            used[ch] = true;
            for (auto [nr, nc] : pos[ch]) {
                if (d[nr][nc] != INF) continue;
                d[nr][nc] = d[r][c] + 1;
                q.emplace(nr, nc);
            }
        }
    }
    cout << (d[h-1][w-1] == INF ? -1 : d[h-1][w-1]) << '\n';
    return 0;
}

复杂度分析

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

---

E - Minimum Swap

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_e

题目大意

输入排列 $P=(P_1,\ldots,P_N)$（$N\le 3\times 10^5$，保证 $P$ 不是恒等排列）。每次操作可以选择 $i<j$ 并交换 $P_i$ 与 $P_j$。设把 $P$ 变成 $(1,2,\ldots,N)$ 所需的最少操作次数为 $K$。问：有多少个 $(i,j)$ 可以作为"某个恰好用 $K$ 次操作完成排序的方案"中的第一次操作？

思路

第 1 步：求最小交换次数 $K$。

构造 $N$ 个点的图，对每个 $i$ 连一条无向边 $(i,P_i)$。由于 $P$ 是排列，每个点的出入度都为 1，所以每个连通分量都是一个环（长度为 1 的自环也算一个环）。设环的个数为 $C$，则有

$$K=N-C.$$

证明思路：

• 一次交换 $(i,j)$ 对环数 $C$ 的影响只有两种：
  • 若 $i,j$ 在同一个环中，该环被拆成两个环，$C$ 增加 1；
  • 若 $i,j$ 在不同的环中，两个环合并成一个，$C$ 减少 1。
• 恒等排列恰好有 $N$ 个环（全是自环），即 $P$ 是恒等排列 $\iff C=N$。
• 只要 $P$ 不是恒等排列（$C<N$），就存在同环的两个顶点（例如取 $i\ne P_i$ 时的 $(i,P_i)$），做一次同环交换就能让 $C$ 加 1。因此从 $C$ 增到 $N$ 至少需要 $N-C$ 次，且恰好 $N-C$ 次可达。

第 2 步：什么样的第一次操作可行？

最优方案必须每一步都让 $C$ 增加 1，所以每一步交换都必须在同一个环内进行；任何一次跨环交换都会让 $C$ 减 1，导致总步数超过 $K$。

反过来，只要第一次操作是"同一环内"的交换，交换后环数变为 $C+1$，剩余排列仍能在 $(N-(C+1))=K-1$ 步内完成（若交换后已经是恒等排列，则 $K-1=0$，结论同样成立）。所以可行的第一次操作恰好是"同一环内的所有点对"，数量为

$$\sum_{\text{环}}\binom{s}{2}=\sum_{\text{环}}\frac{s(s-1)}{2},$$

其中 $s$ 是该环的长度，长度为 1 的自环贡献 0。

实现：用访问标记，从每个未访问的位置出发沿 $P$ 走一圈求出环长 $s$，累加 $s(s-1)/2$ 即可。

注意：答案可能很大（例如 $N=3\times10^5$ 时单个大环的贡献约为 $4.5\times10^{10}$），必须使用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) { cin >> p[i]; --p[i]; }
    vector<bool> vis(n, false);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int v = i, len = 0;
        while (!vis[v]) {
            vis[v] = true;
            v = p[v];
            len++;
        }
        ans += 1LL * len * (len - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

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

---

F - Starry Landscape Photo

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_f

题目大意

$N$ 颗星星从东到西排成一排（$N\le 5\times10^5$），第 $i$ 颗的亮度排名为 $B_i$（$B$ 是 $1..N$ 的排列，数字越小越亮）。拍摄步骤如下：

1. 选择连续区间 $[l,r]$，让第 $l$ 到第 $r$ 颗星星全部入镜；
2. 选择阈值 $b$，只拍摄入镜星星中亮度排名 $\le b$ 的星星。

不允许拍到空集。求可以拍到的不同星星集合的数量。

思路

一个可拍摄的集合 $S$ 必然形如

$$S=\{j\in[l,r] : B_j\le b\}.$$

设 $S$ 中最暗（排名数字最大）的星星为 $i$，即 $B_i=\max_{j\in S}B_j$。此时取 $b=B_i$ 即可（取更大的 $b$ 不会改变集合），于是

$$S=\{j\in[l,r] : B_j\le B_i\}.$$

关键引理：最暗星星为 $i$ 的集合 $S$，与一对位置 $(L,R)$（$L=\min S$，$R=\max S$）一一对应：

• 给定 $(L,R)$，集合 $S$ 就是区间 $[L,R]$ 内所有满足 $B_j\le B_i$ 的星星（因为 $[L,R]\subseteq[l,r]$，这些星星必然都被拍进 $S$）；
• 反之，若 $B_L\le B_i$ 且 $B_R\le B_i$，则集合 $S=\{j\in[L,R]:B_j\le B_i\}$ 的 $\min$ 恰为 $L$、$\max$ 恰为 $R$。

因此，最暗星星为 $i$ 的可拍摄集合数 = 满足以下条件的 $(L,R)$ 对数：

$$L\le i\le R,\qquad B_L\le B_i,\qquad B_R\le B_i.$$

• $L$ 的取法：所有在 $i$ 左侧且 $B_j<B_i$ 的位置，共 $L_i$ 个，再加上 $i$ 本身，共 $L_i+1$ 种；
• $R$ 的取法：所有在 $i$ 右侧且 $B_j<B_i$ 的位置，共 $R_i$ 个，再加上 $i$ 本身，共 $R_i+1$ 种。

所以答案为

$$\sum_{i=1}^{N}(L_i+1)(R_i+1).$$

计算 $L_i$ 与 $R_i$：从左到右扫描，用 Fenwick 树统计"已见过的值"。因为 $B$ 是排列，值小于 $B_i$ 的总数恰为 $B_i-1$，其中左侧有 $L_i$ 个，因此右侧有

$$R_i=(B_i-1)-L_i.$$

扫描到 $i$ 时，先查询 $L_i=$ 树中小于 $B_i$ 的数的个数，再插入 $B_i$。

参考代码

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

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    int sum(int idx) { // 前缀和 [1..idx]
        int r = 0;
        for (; idx > 0; idx -= idx & -idx) r += bit[idx];
        return r;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Fenwick fw(n);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;
        int left = fw.sum(b - 1);      // j < i 且 B_j < B_i 的个数
        int right = (b - 1) - left;    // j > i 且 B_j < B_i 的个数
        ans += 1LL * (left + 1) * (right + 1);
        fw.add(b, 1);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

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

---

G - Linear Inequation

题目链接：https://atcoder.jp/contests/abc436/tasks/abc436_g

题目大意

输入正整数序列 $A=(A_1,\ldots,A_N)$（$N\le 100$，$A_i\le 100$）和正整数 $M$（$M\le 10^{18}$）。求满足

$$\sum_{i=1}^{N}A_i x_i\le M$$

的非负整数序列 $x=(x_1,\ldots,x_N)$ 的个数，答案对 $998244353$ 取模。

思路

（$M$ 太大，无法直接做背包 DP；$N$ 与 $A_i$ 又较小，适合"每次把 $M$ 减半"的倍增思路。下面按官方做法展开。）

记答案函数为 $F(M)=f(A,M)$，并约定 $F(m)=0\ (m<0)$，$F(0)=1$。

第 1 步：把 $M$ 减半的递归。

取 $d=2$。每个 $x_i$ 可唯一地写成 $x_i=2q_i+r_i$，其中 $r_i\in\{0,1\}$。于是

$$\sum A_ix_i=2\sum A_iq_i+\sum A_ir_i\le M \iff \sum A_iq_i\le\left\lfloor\frac{M-\sum A_ir_i}{2}\right\rfloor .$$

令 $S[t]$ 为满足 $\sum A_ir_i=t$ 的 $r\in\{0,1\}^N$ 的个数（即子集和计数），则

$$F(M)=\sum_{t}S[t]\cdot F\!\left(\left\lfloor\frac{M-t}{2}\right\rfloor\right).$$

$S$ 的最大下标为 $\sum A_i\le 10^4$，可以用 $O(N\sum A_i)$ 的背包 DP 求出。

第 2 步：系数向量变换（反向下标不变量）。

我们并不直接求 $F$ 本身，而是维护一个"加权和"不变量。设 $c=(c_i)$ 是有限支撑的系数序列，要求始终有

$$W=\sum_i c_iF(M-i).$$

初始取 $c=[1]$（即 $c_0=1$），此时 $W=F(M)$，正是所求。

把递归式代入不变量：

$$W=\sum_i c_i\sum_t S[t]F\!\left(\left\lfloor\frac{M-i-t}{2}\right\rfloor\right).$$

令 $u=i+t$，则 $M-i-t=M-u$，且 $\sum_{i+t=u}c_iS[t]=(S*c)[u]$ 恰为卷积 $S*c$ 的第 $u$ 项，故

$$W=\sum_u (S*c)[u]\,F\!\left(\left\lfloor\frac{M-u}{2}\right\rfloor\right).$$

第 3 步：一次迭代 = 卷积 + 相邻两项相加。

设 $M'=\lfloor M/2\rfloor$，记 $C=S*c$。对每个 $u$，令

$$s=\left\lfloor\frac{M}{2}\right\rfloor-\left\lfloor\frac{M-u}{2}\right\rfloor,$$

则 $\lfloor(M-u)/2\rfloor=M'-s$，于是

$$W=\sum_s\left(\sum_{\substack{u\\ \lfloor(M-u)/2\rfloor=M'-s}}C_u\right)F(M'-s),$$

即新系数为 $c'_s=\sum_{u:\lfloor(M-u)/2\rfloor=M'-s}C_u$，$(c',M')$ 保持同样的不变量形式。实现时：

1. 计算卷积 $C=S*c$；
2. 对 $0\le u\le \min(M,\text{len}(C)-1)$，把 $C_u$ 累加到槽位 $s=\lfloor M/2\rfloor-\lfloor(M-u)/2\rfloor$ 上；
3. $u>M$ 的部分对应 $F$ 的负参数，贡献为 0，直接丢弃；然后更新 $c\leftarrow c'$、$M\leftarrow M'$。

每轮之后非零系数的最大下标大约变为原来的 $1/2$，所以只需约 $\lceil\log_2 M\rceil\le 60$ 轮。当 $M=0$ 时，

$$W=\sum_i c_iF(-i)=c_0F(0)+0=c_0,$$

输出 $c_0$ 即可。

第 4 步：卷积的加速。

模数 $998244353=119\times2^{23}+1$，原根为 $3$，支持标准 NTT。每轮卷积的规模为 $O(\sum A_i+\text{len}(c))=O(\sum A_i)$，共 $O(\log M)$ 轮，完全可行。

参考代码

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

const int MOD = 998244353;
const int ROOT = 3;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return 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) {
        long long wlen = mod_pow(ROOT, (MOD - 1) / len);
        if (invert) wlen = mod_pow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i + j];
                int v = (int)(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) {
        long long inv_n = mod_pow(n, MOD - 2);
        for (int& x : a) x = (int)(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;
    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] = (long long)fa[i] * fb[i] % MOD;
    ntt(fa, true);
    fa.resize(need);
    return fa;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    // S = 子集和计数：S[t] = #{ T : sum_{i in T} A_i = t }，其中 r_i in {0,1}
    vector<int> S(1, 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        S.resize(S.size() + a, 0);
        for (int j = (int)S.size() - a - 1; j >= 0; j--)
            S[j + a] = (S[j + a] + S[j]) % MOD;
    }
    // 不变量：answer = sum_i coef[i] * F(M - i)
    vector<int> coef(1, 1);
    while (m > 0) {
        long long m2 = m / 2;
        vector<int> C = convolution(S, coef);
        long long k_max = min<long long>(m, (long long)C.size() - 1);
        long long s_max = m2 - (m - k_max) / 2;
        vector<int> ncoef(s_max + 1, 0);
        for (long long k = 0; k <= k_max; k++) {
            long long s = m2 - (m - k) / 2;
            ncoef[(int)s] = (ncoef[(int)s] + C[(int)k]) % MOD;
        }
        coef = move(ncoef);
        m = m2;
    }
    cout << coef[0] << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\sum A_i+\log M\cdot \sum A_i\log\sum A_i)$（其中 $N\sum A_i\le 10^6$，每轮卷积规模 $O(\sum A_i)\le 10^4$，共约 $\log_2 M\le 60$ 轮）
• 空间复杂度：$O(\sum A_i)$