AtCoder Beginner Contest 432 题解

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

AtCoder Beginner Contest 432 题解

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

比赛概览

本场整体难度中等：A、B 两题是典型签到题，考察最基本的排序与"前导零"处理；C 需要一点点代数推导来寻找最优分配；D 把"风暴"这一看似复杂的变化翻译成矩形分裂加并查集求连通块，是本题的思维拐点；E 是经典的值域数据结构题（树状数组/线段树维护频次）；F 结合子集 DP 与操作构造，G 需要生成函数与 NTT，是区分度最高的两题。建议重点掌握 D 的"矩形分裂 + 共边并查集"建模，以及 E 对 $\max(l,\min(r,x))$ 的分类讨论技巧；F、G 则分别复习"子集和 DP"与"NTT 卷积"两大进阶考点。

A - Permute to Maximize

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_a

题目大意

给定三个 $1$ 到 $9$ 的数字 $A,B,C$ ，把它们任意排列并拼接成一个三位整数，求能得到的最大值。

思路

关键观察：比较两个三位数时，位数越高越关键——最高位大的数一定更大；最高位相同时再看次高位……依此类推。因此把三个数字按从大到小排序后依次写下，得到的数就是最大值。

为什么降序排列一定是最大？考虑任意一种排列，若其中存在相邻的两位 $p,q$ （ $p$ 在 $q$ 前面）且 $p$ 位的数字小于 $q$ 位的数字，那么交换这两个数字后， $p$ 位上的数字变大、而更高位保持不变，得到的数一定更大。反复做这样的交换直到序列非增（即降序），所以降序排列是最优解。本题数字个数只有 3 个，也可以直接枚举全部 $3!=6$ 种排列取最大值，但排序更简洁、更通用。

实现上把三个数放入数组，用 sort 降序排序后依次输出即可（它们都是单个数字，直接输出不产生歧义；也可以把它们拼成一个整数输出）。

参考代码

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

int main() {
    vector<int> v(3);
    for (int i = 0; i < 3; i++) cin >> v[i];
    sort(v.rbegin(), v.rend());
    cout << v[0] << v[1] << v[2] << '\n';
    return 0;
}

官方题解给出的 Python 写法：

a, b, c = input().split()
v = sorted([a, b, c])
print(v[2] + v[1] + v[0])

复杂度分析

时间复杂度： $O(1)$ （对 3 个元素排序）
空间复杂度： $O(1)$

B - Permute to Minimize

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_b

题目大意

给定正整数 $X$ （ $1\le X<10^5$ ），把它的十进制表示中的各位数字重新排列，得到一个没有前导零的正整数，求可能的最小值。

思路

与 A 题对称：要让数字最小，最高位要尽可能小；但最高位不能是 $0$ ，所以最高位应取最小的非零数字 $d$ ，剩下的数字再按升序排列即可。

最简洁的实现方式是：先把字符串升序排序，此时形如 $0\cdots 0\,d\,d'\cdots$ （ $d$ 是第一个非零字符，也就是所有非零字符里最小的）；然后找到第一个非零字符，把它与 s[0] 交换。交换之后 s[0] 变成 $d$ ，原来的 s[0]（一个 $0$ ）移到 $d$ 原来所在的位置，其余部分依然保持升序——所以整个结果正好是"最小非零数字 + 其余数字升序"，即答案。

正确性细节：升序排序后，所有 $0$ 都排在前面，后面是非零数字升序。把第一个非零数字提到最前面，最高位成为所有可行最高位中最小的（最高位不能为 $0$ ，故在非零数字中取最小是最优的），而剩余部分仍是非降序列，是最小的排法。

边界情况：若 $X$ 不含 $0$ （如 432），排序后第一个非零字符就是 s[0] 自身，交换后字符串不变；若 $X=100$ ，排序后是 001，交换得 100。答案始终没有前导零。

参考代码

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

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] != '0') {
            swap(s[0], s[i]);
            break;
        }
    }
    cout << s << '\n';
    return 0;
}

官方题解给出的 Python 写法：

x = sorted(input())
for i in range(len(x)):
    if x[i] > '0':
        x[0], x[i] = x[i], x[0]
        break
print(''.join(x))

复杂度分析

时间复杂度： $O(L\log L)$ ，其中 $L\le 5$ 是 $X$ 的位数
空间复杂度： $O(L)$

C - Candy Tribulation

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_c

题目大意

有 $N$ 个孩子，孩子 $i$ 恰好拿到 $A_i$ 颗糖；每颗糖是小糖（重 $X$ 克）或大糖（重 $Y$ 克， $X<Y$ ）。要求每个孩子拿到的总重量相等，问是否存在分配方案；若存在，求能分出去的大糖总数的最大值，否则输出 -1。

思路

设孩子 $i$ 分到 $x_i$ 颗大糖，则他拿到的总重量为

W_i=(A_i-x_i)X+x_iY=A_iX+x_i(Y-X).

条件"所有孩子重量相等"即存在常数 $W$ 使 $W_i=W$ 对每个 $i$ 成立，也就是

x_i=\frac{W-A_iX}{Y-X}.

关键观察一（公共重量的上界）：设 $M=\min_i A_i$ ，取到最小值的那个孩子记为 $m$ （ $A_m=M$ ）。他最多拿 $M$ 颗糖，每颗糖最重为 $Y$ 克，所以他的重量

W=W_m=MX+x_m(Y-X)\le MX+M(Y-X)=MY.

即任何可行方案的公共重量 $W\le MY$ 。

关键观察二（大糖总数随 $W$ 单调）：总大糖数

\sum_i x_i=\sum_i\frac{W-A_iX}{Y-X}=\frac{NW-X\sum_i A_i}{Y-X}

关于 $W$ 严格递增（因为 $Y>X$ ）。所以要让大糖总数最大，只需把公共重量 $W$ 推到上界 $MY$ （若可行）。

最优方案的可行性：取 $W=MY$ ，则孩子 $i$ 需要的大糖数为

x_i=\frac{MY-A_iX}{Y-X}=A_i-\frac{(A_i-M)Y}{Y-X}.

可行当且仅当对每个 $i$ ：

$x_i$ 是整数，即 $(A_i-M)Y$ 能被 $Y-X$ 整除；
$0\le x_i\le A_i$ 。由于 $\frac{(A_i-M)Y}{Y-X}\ge 0$ ， $x_i\le A_i$ 自动成立； $x_i\ge 0$ 等价于 $\frac{(A_i-M)Y}{Y-X}\le A_i$ 。

为什么条件不满足时就一定无解？对任意可行方案，由最小孩子的 $x_m\le M$ 得 $W\le MY$ ；另一方面由每个 $x_i\ge 0$ 得 $W\ge A_iX$ 。这两个界限合并起来，可以推出上面的条件其实对任何方案都必须成立。更直接的说法是：设最小孩子编号为 $m$ ，两个孩子重量相等可改写为

x_i=x_m-\frac{(A_i-M)X}{Y-X},

即各 $x_i$ 的差被完全固定，因此 $\frac{(A_i-M)X}{Y-X}$ 必须都是整数且不超过 $M$ （其中 $M$ 是 $x_m$ 的上界）。这与上面的"整数性 + $x_i\ge 0$ "条件等价，所以一旦有任一条件不满足，就不存在任何分配方案，输出 -1。

全部满足时，答案就是

\sum_i x_i=\sum_i\left(A_i-\frac{(A_i-M)Y}{Y-X}\right).

实现时只需一遍找出 $M$ ，再一遍计算累加。注意数值范围： $(A_i-M)Y\le 10^9\times 10^9=10^{18}$ ，以及答案最多为 $\sum A_i\le 2\times 10^{14}$ ，都要用 64 位整数（long long）。

参考代码

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

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

    int N;
    ll X, Y;
    cin >> N >> X >> Y;
    vector<ll> a(N);
    ll mn = (1LL << 62);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        // x_i = a[i] - (a[i] - mn) * Y / (Y - X)
        ll num = (a[i] - mn) * Y;
        ll den = Y - X;
        if (num % den != 0) {
            cout << -1 << '\n';
            return 0;
        }
        ll minor = num / den;            // 需要"抹掉"的超额部分
        if (minor > a[i]) {
            cout << -1 << '\n';
            return 0;
        }
        ans += a[i] - minor;
    }

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

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(N)$ （存储 $A$ ；先求 $M$ 再算每个 $x_i$ 需要把数组读入内存）

D - Suddenly, A Tempest

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_d

题目大意

在无限大网格上，黑色区域初始为矩形 $0\le x\le X-1,\ 0\le y\le Y-1$ 。接着发生 $N$ 次暴风（ $N\le 14$ ），第 $i$ 次由字符 $C_i\in\{\texttt X,\texttt Y\}$ 与整数 $A_i,B_i$ 描述：

若 $C_i=\texttt X$ ：对 $x<A_i$ 的格子取 $y$ 方向相邻的旧颜色（等价于把黑色区域中 $x<A_i$ 的部分整体沿 $y$ 平移 $-B_i$ ）；对 $x\ge A_i$ 的部分整体沿 $y$ 平移 $+B_i$ 。
若 $C_i=\texttt Y$ ：对 $y<A_i$ 的部分沿 $x$ 平移 $-B_i$ ，对 $y\ge A_i$ 的部分沿 $x$ 平移 $+B_i$ 。

求最终黑色格子的连通块个数，以及每个连通块的大小（升序输出）。

思路

把区域表示成矩形集合。 黑色区域始终可以写成若干个轴平行矩形的并，每个矩形用 $(x_l,x_r,y_l,y_r)$ （闭区间）表示。初始只有一个矩形 $[0,X-1]\times[0,Y-1]$ 。一次暴风对每个矩形做如下操作：沿分割线（X 型是竖线 $x=A$ ，Y 型是横线 $y=A$ ）把矩形切成至多两块，再把各块按各自的方向平移。因此每处理一次暴风，矩形个数最多翻倍， $N$ 次后至多 $2^N$ 个矩形。

为什么矩形之间不会重叠？ 关键在于一次暴风内"平移是分块一致的"：以 Y 型为例，所有 $y<A$ 的碎片都在 $x$ 方向平移 $-B$ ，所有 $y\ge A$ 的碎片都在 $x$ 方向平移 $+B$ 。于是同一类碎片保持原有的相对位置（原来不相交、平移后仍不相交），而不同类碎片的 $y$ 区间分别位于 $y=A$ 的两侧、互不相交；同一矩形切出的两块也分属两类，同样不相交。X 型同理。所以最终矩形集合两两内部不相交，黑色区域就是这些矩形的无重叠并。

连通块 = 共边矩形图的连通分量。 把矩形当作图的顶点，若两个矩形共边——即它们在 $x$ 方向相邻（一个的右边界贴着另一个的左边界）且 $y$ 区间相交，或在 $y$ 方向相邻且 $x$ 区间相交——则在它们之间连一条边。矩形之间只有共边时，其中的格子才通过曼哈顿距离为 1 的移动互相到达，所以网格中的连通块与这个图的连通分量一一对应。共边判定是 $O(1)$ 的：

$xadj$ ： $s.x_r+1=t.x_l$ 或 $t.x_r+1=s.x_l$ （ $x$ 方向相邻）；
$yadj$ ： $s.y_r+1=t.y_l$ 或 $t.y_r+1=s.y_l$ （ $y$ 方向相邻）；
$xover$ ： $s.x_l\le t.x_r$ 且 $t.x_l\le s.x_r$ （ $x$ 区间相交）； $yover$ 同理；
共边当且仅当 $(xadj\wedge yover)\vee(yadj\wedge xover)$ 。

注意仅仅"角对角相触"的矩形不算共边：此时两个方向都只是相邻而非相交，两个矩形里没有任何一对格子曼哈顿距离为 1，因而不连通。

求块大小。 每个矩形的面积为 $(x_r-x_l+1)(y_r-y_l+1)$ ，一个连通块的大小就是块内各矩形面积之和。可以验证（每次暴风都是分段平移，是保面积的）总面积始终等于初始的 $X\cdot Y\le 10^{16}$ ，用 long long 即可。

实现上用并查集（DSU）合并所有共边的矩形对，再对每个根累加面积，排序后输出。

复杂度：矩形数 $R\le 2^N$ ，两两枚举共边为 $O(R^2)$ ，总复杂度 $O(N\cdot 2^N+4^N)$ 。对 $N=14$ ， $R$ 的实际值远小于 $2^{14}$ （官方更精细的分析给出 $N=14$ 时 $R\le 471$ ），因此该做法绰绰有余。

参考代码

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

struct Rect {
    ll xl, xr, yl, yr;
};

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) p[a] = b;
    }
};

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

    int N;
    ll X, Y;
    cin >> N >> X >> Y;
    vector<char> c(N);
    vector<ll> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> c[i] >> A[i] >> B[i];

    vector<Rect> cur = {{0, X - 1, 0, Y - 1}};
    for (int qi = 0; qi < N; qi++) {
        vector<Rect> nxt;
        for (const Rect& r : cur) {
            if (c[qi] == 'X') {
                if (r.xr < A[qi]) {
                    nxt.push_back({r.xl, r.xr, r.yl - B[qi], r.yr - B[qi]});
                } else if (r.xl >= A[qi]) {
                    nxt.push_back({r.xl, r.xr, r.yl + B[qi], r.yr + B[qi]});
                } else {
                    nxt.push_back({r.xl, A[qi] - 1, r.yl - B[qi], r.yr - B[qi]});
                    nxt.push_back({A[qi], r.xr, r.yl + B[qi], r.yr + B[qi]});
                }
            } else { // 'Y'
                if (r.yr < A[qi]) {
                    nxt.push_back({r.xl - B[qi], r.xr - B[qi], r.yl, r.yr});
                } else if (r.yl >= A[qi]) {
                    nxt.push_back({r.xl + B[qi], r.xr + B[qi], r.yl, r.yr});
                } else {
                    nxt.push_back({r.xl - B[qi], r.xr - B[qi], r.yl, A[qi] - 1});
                    nxt.push_back({r.xl + B[qi], r.xr + B[qi], A[qi], r.yr});
                }
            }
        }
        cur = move(nxt);
    }

    int R = (int)cur.size();
    DSU dsu(R);
    for (int i = 0; i < R; i++) {
        for (int j = i + 1; j < R; j++) {
            const Rect& s = cur[i];
            const Rect& t = cur[j];
            bool xadj = (s.xr + 1 == t.xl) || (t.xr + 1 == s.xl);
            bool yadj = (s.yr + 1 == t.yl) || (t.yr + 1 == s.yl);
            bool xover = (s.xl <= t.xr) && (t.xl <= s.xr);
            bool yover = (s.yl <= t.yr) && (t.yl <= s.yr);
            if ((xadj && yover) || (yadj && xover)) dsu.merge(i, j);
        }
    }

    vector<ll> area(R);
    for (int i = 0; i < R; i++) {
        area[i] = (cur[i].xr - cur[i].xl + 1) * (cur[i].yr - cur[i].yl + 1);
    }

    vector<vector<int>> groups(R);
    for (int i = 0; i < R; i++) groups[dsu.find(i)].push_back(i);

    vector<ll> sz;
    for (int i = 0; i < R; i++) {
        if (groups[i].empty()) continue;
        ll s = 0;
        for (int idx : groups[i]) s += area[idx];
        sz.push_back(s);
    }
    sort(sz.begin(), sz.end());

    cout << sz.size() << '\n';
    for (int i = 0; i < (int)sz.size(); i++) {
        if (i) cout << ' ';
        cout << sz[i];
    }
    cout << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N\cdot 2^N + 4^N)$ （矩形数 $R\le 2^N$ ，两两枚举共边 $O(R^2)$ ；实际 $N=14$ 时 $R\le 471$ ）
空间复杂度： $O(2^N)$

E - Clamp

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_e

题目大意

给定长度为 $N$ 的整数序列 $A$ ，值域 $0\le A_i\le 5\times10^5$ 。有 $Q$ 个按顺序处理的询问：

1 x y：把 $A_x$ 改成 $y$ ；
2 l r：求 $\displaystyle \sum_{i=1}^{N}\max(l,\min(r,A_i))$ 。

思路

先处理一个简单情形：若 $l>r$ ，则对任意 $x$ 都有 $\min(r,x)\le r<l$ ，所以 $\max(l,\min(r,x))=l$ ，答案就是 $l\times N$ 。

下面假设 $l\le r$ 。把 $\max(l,\min(r,A_i))$ 按 $A_i$ 落在哪个区间分类：

\max(l,\min(r,A_i))=\begin{cases} l, & A_i<l \\ A_i, & l\le A_i\le r \\ r, & A_i>r \end{cases}

记 $C_j$ 为值 $j$ 在 $A$ 中出现的次数，则

\sum_{i=1}^{N}\max(l,\min(r,A_i)) =l\sum_{j<l}C_j+\sum_{j=l}^{r}j\,C_j+r\sum_{j>r}C_j.

三项分别需要：值在 $[0,l-1]$ 的个数、值在 $[l,r]$ 的加权和、值在 $[r+1,5\times10^5]$ 的个数（可用总数 $N$ 减去" $\le r$ 的个数"得到）。

于是需要维护一个支持如下操作的数据结构：

单点更新 $C_j$ （某处 $\pm1$ ）；
区间查询 $\sum C_j$ ；
区间查询 $\sum j\,C_j$ 。

用两个树状数组（Fenwick 树）即可：一个维护个数 $C_j$ ，一个维护加权和 $j\cdot C_j$ 。值 $v$ 映射到下标 $v+1$ 以兼容 $v=0$ 。查询时三个区间分别用前缀和组合出来，一次 2 操作 $O(\log V)$ ，一次 1 操作是两次单点更新，也 $O(\log V)$ 。（官方题解使用带二元组 $(\textstyle\sum C_j,\ \sum jC_j)$ 的线段树，本质相同。）

参考代码

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

struct BIT {
    int n;
    vector<ll> bit;
    BIT(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, ll val) {            // 1-based 单点加
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    ll sum(int idx) const {                // 前缀和 [1, idx]
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    ll range(int l, int r) const {         // 区间和 [l, r]
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};

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

    int N, Q;
    cin >> N >> Q;
    const int V = 500000;

    vector<int> a(N);
    BIT cnt(V + 1), wsum(V + 1);           // 值 v -> 下标 v+1
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        cnt.add(a[i] + 1, 1);
        wsum.add(a[i] + 1, a[i]);
    }

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            --x;
            cnt.add(a[x] + 1, -1);
            wsum.add(a[x] + 1, -a[x]);
            a[x] = y;
            cnt.add(a[x] + 1, 1);
            wsum.add(a[x] + 1, a[x]);
        } else {
            int l, r;
            cin >> l >> r;
            ll ans;
            if (l > r) {
                ans = (ll)l * N;
            } else {
                ll cLess    = cnt.range(1, l);           // 值 < l
                ll wMid     = wsum.range(l + 1, r + 1);  // 值 in [l, r]
                ll cGreater = N - cnt.range(1, r + 1);   // 值 > r
                ans = (ll)l * cLess + wMid + (ll)r * cGreater;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O((N+Q)\log V)$ ，其中 $V=5\times10^5$
空间复杂度： $O(V)$

F - Candy Redistribution

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_f

题目大意

有 $N$ 个孩子（ $N\le 20$ ），孩子 $i$ 有 $A_i$ 颗糖。一次操作：选两个不同孩子 $x,y$ 与正整数 $z$ （ $z$ 不超过 $x$ 当前糖数），从 $x$ 拿 $z$ 颗给 $y$ 。问能否通过若干次操作使所有人糖数相等；若能，输出操作数最少的一组操作序列（多解输出任意一组）。

思路

可行性。 糖的总数 $S=\sum A_i$ 在操作中不变，最终每个人都是 $X=S/N$ ，所以 $S$ 必须能被 $N$ 整除；若 $S\bmod N\neq 0$ ，输出 -1。若整除，后面会看到一定有解。

操作数的下界。 把每次操作看成在 $x,y$ 之间连一条边，得到一张 $N$ 个顶点的（多重）图。设其连通分量为 $V_1,\dots,V_s$ 。在一个连通分量内部，糖的总量守恒，且最终分量内每个点的糖数都变为 $X$ ，所以

\sum_{v\in V_k}A_v=X\cdot |V_k|.

又 $k$ 个顶点的连通图至少有 $k-1$ 条边，因此总操作数

q\ge\sum_k(|V_k|-1)=N-s.

达到下界。 反过来，只要把点集划分成若干块，每块满足 $\sum_{v\in V}A_v=X|V|$ ，就能用 $|V|-1$ 次操作把这块内部全部变成 $X$ 。做法：把块内元素按 $A$ 从大到小排成 $v_1,\dots,v_t$ ，依次执行操作 $(v_i,\ v_{i+1},\ a_{v_i}-X)$ 。

设 $e_j=A_{v_j}-X$ ，则 $\sum_j e_j=0$ 且 $e_1\ge e_2\ge\cdots\ge e_t$ 。关键性质是所有前缀和 $E_i=e_1+\cdots+e_i\ge 0$ ：若某个 $E_i<0$ ，则前 $i$ 个数的平均为负，于是 $e_i<0$ ，其后的 $e_{i+1},\dots,e_t\le e_i<0$ 全部为负，总和必为负，矛盾。因此在第 $i$ 步时， $v_i$ 的当前糖数为 $X+E_i\ge X$ ，转给 $v_{i+1}$ 恰好 $E_i$ 颗（ $v_i$ 自己剩下 $X$ ），第 $t$ 个孩子最终得到 $X+E_t=X$ 。如此 $t-1$ 步后整块都变成 $X$ 。

若某处 $E_i=0$ ，那一步其实要"转 0 颗"，不合法。但在**最优划分（块数最多）**中不会出现这种情况：若某块存在真子集使前缀和 $E_i=0$ ，则这个前缀对应的孩子集合本身也满足 $\sum A=X\cdot i$ ，可以把它从块里拆出来，从而增加块数，这与"块数最多"矛盾。因此最优划分下所有 $E_i\ge 1$ ，操作全部合法。

求块数最多的划分。 这是个子集和型状压 DP。记 $\textit{subsum}[mask]=\sum_{i\in mask}(A_i-X)$ ，令

dp[mask]=\min_{\,i\in mask\,}\{\,dp[mask\setminus\{i\}]\,\}+[\ \textit{subsum}[mask]\neq 0\ ],\qquad dp[0]=0.

这个 DP 的含义：按某种顺序逐个把元素加入集合，每加入一个元素，若当前集合的子集和不为 0，说明这一块还没凑满，操作数记 1；一旦某个瞬间子集和恰好为 0，说明正好凑成一块，这块的收尾就不再多记。可以验证 $dp[\text{全集}]=N-s^*$ ，其中 $s^*$ 是最大块数；同时用 $prev[mask]$ 记录使转移最优的最后一个元素，便于回溯。

回溯：从全集出发，反复取 prev 收集元素，直到剩余集合的 $\textit{subsum}=0$ ，就得到一块；对每块按 $A$ 降序排序后，用上面的方法输出操作序列。

参考代码

#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> a(N);
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % N != 0) {
        cout << -1 << '\n';
        return 0;
    }
    ll X = sum / N;

    int S = 1 << N;
    vector<ll> subsum(S, 0), dp(S, N + 1);
    vector<int> prev(S, -1);
    dp[0] = 0;

    for (int mask = 1; mask < S; mask++) {
        subsum[mask] = 0;
        for (int i = 0; i < N; i++)
            if (mask >> i & 1) subsum[mask] += a[i] - X;

        int add = (subsum[mask] == 0 ? 0 : 1);
        for (int i = 0; i < N; i++) {
            if (mask >> i & 1) {
                ll cand = dp[mask ^ (1 << i)] + add;
                if (cand < dp[mask]) {
                    dp[mask] = cand;
                    prev[mask] = i;
                }
            }
        }
    }

    vector<array<ll, 3>> ops;              // (x, y, z)
    int mask = S - 1;
    while (mask) {
        vector<int> grp;
        while (true) {
            int i = prev[mask];
            grp.push_back(i);
            mask ^= (1 << i);
            if (subsum[mask] == 0) break;
        }
        sort(grp.begin(), grp.end(),
             [&](int u, int v) { return a[u] > a[v]; });
        ll carry = a[grp[0]] - X;          // 当前孩子需要转出的糖数
        for (int k = 1; k < (int)grp.size(); k++) {
            ops.push_back({grp[k - 1], grp[k], carry});
            carry += a[grp[k]] - X;
        }
    }

    cout << ops.size() << '\n';
    for (auto [x, y, z] : ops) {
        cout << x + 1 << ' ' << y + 1 << ' ' << z << '\n';
    }
    return 0;
}

复杂度分析

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

G - Sum of Binom(A, B)

题目链接：https://atcoder.jp/contests/abc432/tasks/abc432_g

题目大意

给定长度分别为 $N,M$ 的正整数序列 $A,B$ （元素 $\le 5\times10^5$ ），求

\sum_{i=1}^{N}\sum_{j=1}^{M}\binom{A_i}{B_j}\bmod 998244353,

其中 $\binom{x}{y}=0$ （当 $x<y$ 时）。

思路

直接枚举 $N\times M$ 个二元组是 $O(NM)$ ，不可行。利用"值域只有 $5\times10^5$ "这一特点按值分组。

记 $C_a(j)$ 为 $A$ 中等于 $j$ 的元素个数， $C_b(j)$ 同理， $K=\max(\max A,\max B)$ 。把求和重写为

\sum_{i,j}\binom{A_i}{B_j} =\sum_{i=1}^{K}\sum_{j=1}^{i}C_a(i)\,C_b(j)\binom{i}{j},

其中内层只需枚举 $j\le i$ （ $j>i$ 时组合数为 0，自然省略）。用阶乘展开 $\binom{i}{j}=\dfrac{i!}{j!(i-j)!}$ ，并提取与 $j$ 无关的因子：

\begin{aligned} \sum_{i,j}\binom{A_i}{B_j} &=\sum_{i=1}^{K}C_a(i)\cdot i!\cdot\sum_{j=1}^{i}\frac{C_b(j)}{j!(i-j)!}\\ &=\sum_{i=1}^{K}C_a(i)\cdot i!\cdot\sum_{j+k=i}\left(\frac{C_b(j)}{j!}\cdot\frac{1}{k!}\right). \end{aligned}

内层 $\sum_{j+k=i}$ 是一个标准的卷积。定义两个多项式

f(x)=\sum_{j=0}^{K}\frac{C_b(j)}{j!}x^j,\qquad g(x)=\sum_{j=0}^{K}\frac{x^j}{j!},

则 $h=f\cdot g$ 的第 $i$ 项系数 $[x^i]h=\sum_{j+k=i}\frac{C_b(j)}{j!}\cdot\frac{1}{k!}$ 恰好是所需的内层和。于是

\text{Ans}=\sum_{i=1}^{K}C_a(i)\cdot i!\cdot[x^i]h.

用 NTT（数论变换）在模 $998244353$ 下做一次多项式乘法即可。 $998244353=119\times2^{23}+1$ ，原根为 $3$ ，是经典的 NTT 友好模数；也可以直接调用 AC Library 的 convolution。

实现细节：预处理 $0..K$ 的阶乘 fac 与逆元阶乘 ifac；令 $f[i]=\textit{ifac}[i]\cdot C_b(i)$ ， $g[i]=\textit{ifac}[i]$ 。注意 $C_b(0)=0$ （ $B$ 的元素 $\ge1$ ），不影响结果；卷积中 $j=0$ 的项会被正确处理，自动实现"只累加 $B_j\le A_i$ 的组合数"。

参考代码

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

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

ll mod_pow(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 inverse) {
    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 = mod_pow(ROOT, (MOD - 1) / len);
        if (inverse) wlen = mod_pow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; j++) {
                ll u = a[i + j];
                ll v = a[i + j + half] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + half] = (u - v + MOD) % MOD;
                w = w * wlen % MOD;
            }
        }
    }
    if (inverse) {
        ll inv_n = mod_pow(n, MOD - 2);
        for (ll& x : a) x = x * inv_n % MOD;
    }
}

vector<ll> convolution(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;
}

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

    const int MAXV = 500000;
    int N, M;
    cin >> N >> M;
    vector<int> ca(MAXV + 1, 0), cb(MAXV + 1, 0);
    for (int i = 0; i < N; i++) { int x; cin >> x; ca[x]++; }
    for (int i = 0; i < M; i++) { int x; cin >> x; cb[x]++; }

    vector<ll> fac(MAXV + 1), ifac(MAXV + 1);
    fac[0] = 1;
    for (int i = 1; i <= MAXV; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXV] = mod_pow(fac[MAXV], MOD - 2);
    for (int i = MAXV; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;

    vector<ll> f(MAXV + 1), g(MAXV + 1);
    for (int i = 0; i <= MAXV; i++) {
        f[i] = ifac[i] * cb[i] % MOD;
        g[i] = ifac[i];
    }

    vector<ll> h = convolution(f, g);

    ll ans = 0;
    for (int i = 0; i <= MAXV; i++) {
        ans = (ans + (ll)ca[i] * fac[i] % MOD * h[i]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N+M+K\log K)$ ，其中 $K\le 5\times10^5$ （NTT 部分 $O(K\log K)$ ）
空间复杂度： $O(K)$