二项式反演：从“至少”到“恰好”的组合计数利器

1. 项目概述：从“恰好”到“至少”的思维转换

在组合数学和概率论的实际问题里，我们常常会遇到两种看似相似、实则互为“镜像”的计数场景。比如，统计一个班级里“恰好有3个同学获得A”的情况，和统计“至少有3个同学获得A”的情况。直接计算“恰好”往往非常困难，因为它要求一个精确的边界；而计算“至少”则相对容易，因为它可以通过容斥原理或者更简单的方法进行累积。二项式反演（Binomial Inversion）正是连接这两个世界的桥梁，它提供了一套精确的公式，让我们能够从容易计算的“至少/至多”计数结果，反推出难以直接计算的“恰好”计数结果。

这个工具的强大之处在于其普适性和简洁性。它不仅仅是一个数学公式，更是一种重要的组合学思想。当你掌握了它，再看许多复杂的包含-排除问题、错排问题甚至是一些概率期望问题，会有一种豁然开朗的感觉。它把一种需要复杂分类讨论的思维过程，转化为了一个可以机械套用的代数运算。无论你是正在准备算法竞赛的学生，还是从事数据分析需要处理复杂计数问题的工程师，理解二项式反演都能让你的工具箱里多出一件称手的利器。

2. 核心原理：公式、推导与直观理解

2.1 两种标准形式及其互推

二项式反演通常以两种对称的形式出现，它们分别处理“至少”和“至多”到“恰好”的转换。

形式一：从“至少”反演到“恰好”这是最常见的形式。设 ( f(n) ) 表示“至少”有 ( n ) 个元素满足某种性质的方案数，( g(n) ) 表示“恰好”有 ( n ) 个元素满足该性质的方案数。那么它们满足以下关系： [ f(n) = \sum_{i=n}^{m} \binom{i}{n} g(i) \quad \text{对于所有 } n = 0, 1, ..., m ] 其反演公式为： [ g(n) = \sum_{i=n}^{m} (-1)^{i-n} \binom{i}{n} f(i) ] 这里的 ( m ) 是元素总数的上界。这个公式的直观意义是：要得到“恰好n个”，我们从“至少n个”中，减去那些“实际上多于n个”的部分。由于“至少n个”中包含了“恰好n+1个”、“恰好n+2个”……的情况，并且这些“恰好k个”在计算“至少n个”时被重复计算了 ( \binom{k}{n} ) 次（从k个中任选n个作为那“至少”的n个），所以我们需要用带符号的容斥来精确扣除。

形式二：从“至多”反演到“恰好”另一种对称的形式。设 ( F(n) ) 表示“至多”有 ( n ) 个元素满足性质的方案数，( G(n) ) 表示“恰好”有 ( n ) 个的方案数。它们的关系是： [ F(n) = \sum_{i=0}^{n} \binom{n}{i} G(i) ] 其反演公式为： [ G(n) = \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} F(i) ] 这两种形式本质上是等价的，可以通过变量替换相互转化。通常，我们根据具体问题中哪个量（“至少”或“至多”）更容易计算，来决定使用哪一种形式。

2.2 组合证明与生成函数视角

理解为什么这个公式成立，比记住公式更重要。这里给出一个经典的组合证明思路（以形式一为例）：

我们已知 ( f(n) = \sum_{i=n}^{m} \binom{i}{n} g(i) )。现在将反演公式 ( g(n) = \sum_{i=n}^{m} (-1)^{i-n} \binom{i}{n} f(i) ) 代入右边进行验证： [ \begin{aligned} \sum_{i=n}^{m} \binom{i}{n} g(i) &= \sum_{i=n}^{m} \binom{i}{n} \left[ \sum_{j=i}^{m} (-1)^{j-i} \binom{j}{i} f(j) \right] \ &= \sum_{j=n}^{m} f(j) \sum_{i=n}^{j} \binom{i}{n} \binom{j}{i} (-1)^{j-i} \ &= \sum_{j=n}^{m} f(j) \binom{j}{n} \sum_{i=n}^{j} \binom{j-n}{i-n} (-1)^{j-i} \quad \text{(利用组合恒等式)} \ &= \sum_{j=n}^{m} f(j) \binom{j}{n} \sum_{k=0}^{j-n} \binom{j-n}{k} (-1)^{(j-n)-k} \quad \text{(令 k = i-n)} \ &= \sum_{j=n}^{m} f(j) \binom{j}{n} (1 - 1)^{j-n} \quad \text{(二项式定理)} \ &= f(n) \quad \text{(因为仅当 j=n 时，} (1-1)^{0}=1 \text{，否则为0)} \end{aligned} ] 这个证明过程清晰地展示了系数如何通过二项式定理的展开与收缩相互抵消，最终只剩下我们想要的项。它体现了组合数学中一种深刻的对偶性。

从生成函数的角度看，二项式反演可以看作是某种变换的逆。将序列 ( {g(n)} ) 和 ( {f(n)} ) 联系起来的关系，类似于一种二项式卷积。这种视角在理论研究中非常有力，能够统一处理一系列相关问题。

注意：初次接触推导过程可能会觉得有些繁琐，但不必强求每一步都立刻理解。关键是要抓住核心思想：利用带符号的二项式系数进行容斥，以精确分离出“恰好”的情况。在实际应用中，我们更多是直接套用公式，但了解其来源能让你在遇到变种问题时知道如何调整。

3. 典型应用场景与建模方法

二项式反演的价值在于它能将许多复杂问题化繁为简。下面通过几个经典场景，看看如何将实际问题抽象成反演模型。

3.1 场景一：错排问题（Derangement）

问题：有 ( n ) 封信和 ( n ) 个对应的信封，所有信都装错信封的方案数 ( D_n ) 是多少？

建模与求解：

1. 定义“至少”：设 ( f(k) ) 表示“至少有 ( k ) 封信装对了信封”的方案数。这很容易计算：先从 ( n ) 封信中选出 ( k ) 封保证装对，有 ( \binom{n}{k} ) 种选法；剩下的 ( n-k ) 封信任意装，有 ( (n-k)! ) 种装法。因此 ( f(k) = \binom{n}{k} (n-k)! = \frac{n!}{k!} )。
2. 定义“恰好”：设 ( g(k) ) 表示“恰好有 ( k ) 封信装对”的方案数。我们最终要求的是 ( g(0) )，即全部装错的方案数 ( D_n )。
3. 应用反演公式（形式一）：根据关系 ( f(k) = \sum_{i=k}^{n} \binom{i}{k} g(i) )，代入 ( k=0 )： [ f(0) = \sum_{i=0}^{n} \binom{i}{0} g(i) = \sum_{i=0}^{n} g(i) ] 但 ( f(0) = n! )（所有信任意装）。这并没有直接给出 ( g(0) )。我们需要完整的反演。 由反演公式： [ g(k) = \sum_{i=k}^{n} (-1)^{i-k} \binom{i}{k} f(i) = \sum_{i=k}^{n} (-1)^{i-k} \binom{i}{k} \frac{n!}{i!} ]
4. 计算目标：令 ( k=0 )： [ D_n = g(0) = \sum_{i=0}^{n} (-1)^{i} \binom{i}{0} \frac{n!}{i!} = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} ] 这就是著名的错排数公式。当 ( n ) 很大时，( D_n \approx \frac{n!}{e} )。

实操心得：在这个问题中，选择“至少装对k封”作为 ( f(k) ) 是建模的关键，因为它比计算“恰好”容易得多。二项式反演充当了一个“解方程”的工具，从 ( f ) 的序列中解出了 ( g ) 的序列。

3.2 场景二：子集约束计数

问题：设全集 ( U ) 有 ( m ) 个元素。对于每个元素，我们知道它是否可能出现在某个子集中（有 ( m ) 个布尔条件）。定义 ( F(S) ) 为满足“至少包含了集合 ( S ) 中所有元素”的子集个数。如何求出恰好满足某个特定属性集合 ( T ) 的子集个数 ( G(T) )？

建模与求解：

1. 建立关系：如果“至少包含S”意味着子集必须包含S中的所有元素，那么对于任意集合 ( T \supseteq S )，这个子集自然也“至少包含S”。因此，( F(S) ) 可以表示为所有以 ( S ) 为子集的集合 ( T ) 对应的 ( G(T) ) 之和。但这里不是简单的二项式系数，因为集合大小不一。我们需要更一般的莫比乌斯反演。
2. 连接二项式反演：如果我们只关心集合的大小，而不是具体是哪些元素，问题就简化了。设 ( f(k) ) 为“至少包含某个特定大小为 ( k ) 的集合”的子集数量（由于对称性，这个数与具体是哪个k元集无关）。设 ( g(k) ) 为“恰好包含某个特定大小为 ( k ) 的集合”的子集数量。那么，一个“恰好包含某个i元集”的子集，在计算“至少包含某个k元集”时，会被计数多少次呢？这要求那个k元集是那个i元集的子集。从一个i元集中选出一个特定的k元子集，只有1种方式（如果固定了那个k元集的话）。但我们的 ( f(k) ) 定义是“至少包含某个特定的k元集”，所以对于每个大小为i的超集，只有1个特定的k元子集符合要求。因此，关系为： [ f(k) = \sum_{i=k}^{m} \binom{m-k}{i-k} g(i) ] 这里 ( \binom{m-k}{i-k} ) 表示：固定了一个k元集后，要形成一个包含它的i元集，需要从剩下的 ( m-k ) 个元素中再选 ( i-k ) 个。这其实就是二项式反演形式一的变体，系数 ( \binom{i}{k} ) 变成了 ( \binom{m-k}{i-k} )，但通过变量代换可以化为标准形式。
3. 应用与意义：这个场景展示了二项式反演在更一般的集合计数问题中的核心思想：通过一个容易计算的、带有“至少/至多”条件的计数函数，去求解精确的计数函数。在算法竞赛中，许多涉及“钦定”、“强制满足”某些条件的计数题，最终都归结于这一模型。

注意事项：在将实际问题建模为二项式反演时，最易出错的地方是确定求和系数 ( \binom{i}{n} ) 是否正确。你必须清晰地回答：一个“恰好为i”的方案，在计算“至少为n”时，被重复计算了多少次？这个次数必须是 ( \binom{i}{n} ) 或其等价形式。如果系数不对，说明建模有误。

3.3 场景三：概率与期望中的二项式反演

二项式反演在概率论中也有巧妙的应用，特别是在处理事件“至少发生k次”的概率时。

问题：进行 ( n ) 次独立伯努利试验，每次成功的概率为 ( p )。设 ( P_{\ge k} ) 表示“至少成功 ( k ) 次”的概率，( P_{=k} ) 表示“恰好成功 ( k ) 次”的概率。显然 ( P_{=k} = \binom{n}{k} p^k (1-p)^{n-k} )，而 ( P_{\ge k} = \sum_{i=k}^{n} P_{=i} )。这本身就是二项式反演关系 ( f(k)=P_{\ge k}, g(k)=P_{=k} ) 的一个实例。

更高级的应用：考虑一个随机图模型。设 ( f(k) ) 为“图中至少存在 ( k ) 个特定结构（比如三角形）”的概率。直接计算 ( f(k) ) 可能极其复杂，因为事件之间不独立。但有时我们可以计算“图中恰好存在 ( k ) 个特定结构”的概率生成函数，或者其矩。这时，二项式反演可以作为连接矩和分布的工具，在随机图论和极值组合中有所应用。虽然这个例子比较深入，但它说明了二项式反演思想的普适性——它处理的是一种线性变换及其逆变换。

4. 实战演练：从问题到代码的完整过程

让我们通过一个具体的算法竞赛风格题目，将二项式反演的应用流程完整走一遍，包括思路分析、公式推导和代码实现。

4.1 问题定义

假设我们有 ( n ) 个不同的球和 ( m ) 个不同的盒子。现在要将所有球放入盒子中，要求每个盒子至少有一个球。定义一种放置方案的“溢出度”为有超过1个球的盒子的数量。现在对于每个 ( k ) (0 ≤ k ≤ m)，我们需要求出“溢出度恰好为 ( k ) ”的放置方案数。注意，球是不同的，盒子也是不同的。

输入：整数 ( n, m ) (1 ≤ m ≤ n ≤ 5000)。输出：对于每个 ( k ) 从 0 到 m，输出一个整数，表示方案数对某个大质数 ( MOD ) (如 ( 10^9+7 )) 取模的结果。

4.2 逐步分析与建模

第一步：思考直接计算“恰好”的难度“溢出度恰好为k”意味着：在这m个盒子中，恰好有k个盒子包含了至少2个球，而剩下的 ( m-k ) 个盒子都只包含了恰好1个球。由于球和盒子都不同，我们需要同时考虑：1) 选出哪k个盒子是“溢出”的；2) 如何分配球使得选中的盒子每个至少2个球，未选中的盒子每个恰好1个球。这涉及到复杂的多重集合划分，直接组合计算非常困难。

第二步：构造容易计算的“至少”我们定义：

• 设 ( f(i) ) 表示“至少有 ( i ) 个盒子是溢出的”（即钦定某i个盒子每个至少放2个球，其余 ( m-i ) 个盒子随意放，可以为空）的方案数。
• 注意，这里“至少”是针对“被钦定的盒子集合”而言的，而不是全局至少有i个溢出盒。我们通过“钦定”来构造 ( f(i) )。

为什么 ( f(i) ) 容易算？

1. 首先，从m个盒子中钦定i 个盒子作为“溢出盒”。有 ( \binom{m}{i} ) 种钦定方式。
2. 为了保证这 i 个被钦定的盒子每个至少2个球，我们可以先拿出 ( 2i ) 个球，每个被钦定的盒子先分配2个球。由于球不同，分配这 ( 2i ) 个球到 i 个盒子的方式数为：将 ( 2i ) 个不同的球分成 i 个有序的组（对应i个盒子），每组恰好2个球。这个方案数是 ( \frac{(2i)!}{2^i} ) （先全排列，再除以每个盒子内2个球的顺序）。
3. 现在还剩下 ( n - 2i ) 个球。这 ( n-2i ) 个球可以任意分配到全部 m 个盒子中（包括之前被钦定的 i 个盒子），没有任何限制。每个球有 m 种选择，所以方案数是 ( m^{n-2i} )。
4. 因此，( f(i) = \binom{m}{i} \cdot \frac{(2i)!}{2^i} \cdot m^{n-2i} )，前提是 ( n \ge 2i )，否则 ( f(i) = 0 )。

第三步：建立反演关系我们最终要求的是 ( g(k) )：“恰好有 k 个盒子溢出”。注意，这里的“恰好”是全局的，不是针对钦定集合的。

考虑一个具体的方案，它的全局溢出盒集合是 ( S )，且 ( |S| = j )。这个方案会被哪些 ( f(i) ) 计数到呢？它会被所有满足“钦定集合 ( T \subseteq S )”的 ( f(|T|) ) 计数到。因为只要你钦定的溢出盒集合 ( T ) 是实际溢出盒集合 ( S ) 的子集，这个方案就满足“被钦定的盒子（T）每个至少2个球”的条件。

对于一个大小为 ( j ) 的实际溢出集合 ( S )，它包含的大小为 ( i ) 的子集 ( T ) 的个数是 ( \binom{j}{i} )。因此，每一个“恰好有 j 个溢出盒”的方案，在计算 ( f(i) ) 时被计算了 ( \binom{j}{i} ) 次。

于是我们得到关系式： [ f(i) = \sum_{j=i}^{m} \binom{j}{i} g(j) ] 这正是二项式反演的标准形式一！其中 ( f(i) ) 是已知的（我们已推导出公式），( g(j) ) 是未知的。

第四步：应用反演公式求解根据二项式反演公式一： [ g(k) = \sum_{i=k}^{m} (-1)^{i-k} \binom{i}{k} f(i) ] 现在，我们只需要预处理组合数、阶乘、幂，然后对于每个 ( k )，用这个公式计算 ( g(k) ) 即可。时间复杂度为 ( O(m^2) )，对于 ( n, m \leq 5000 ) 是可行的（约2500万次运算，在合理优化下可以通过）。

4.3 代码实现与细节处理

#include <bits/stdc++.h> using namespace std; using ll = long long; const int MOD = 1e9 + 7; const int MAXN = 5005; ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } // 预处理阶乘、逆元、组合数、2的逆幂、m的幂 ll fac[MAXN*2], invfac[MAXN*2]; // 注意 (2i)! 可能用到 2*m ll inv2; // 2的逆元 ll pow_m[MAXN*2]; // m的幂 ll C[MAXN][MAXN]; ll f[MAXN], g[MAXN]; void init(int n, int m) { // 组合数 C[i][j] for (int i = 0; i <= m; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) { C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } // 阶乘 fac[0] = 1; for (int i = 1; i <= 2*m; ++i) fac[i] = fac[i-1] * i % MOD; // 逆元阶乘 invfac[2*m] = qpow(fac[2*m], MOD-2); for (int i = 2*m-1; i >= 0; --i) invfac[i] = invfac[i+1] * (i+1) % MOD; // 2的逆元 inv2 = qpow(2, MOD-2); // m的幂 pow_m[0] = 1; for (int i = 1; i <= n; ++i) pow_m[i] = pow_m[i-1] * m % MOD; } int main() { int n, m; cin >> n >> m; init(n, m); // 1. 计算 f(i) for (int i = 0; i <= m; ++i) { if (2 * i > n) { f[i] = 0; continue; } // f(i) = C(m, i) * (2i)! / (2^i) * m^(n-2i) ll term1 = C[m][i]; // 选择钦定的i个盒子 ll term2 = fac[2*i]; // (2i)! ll term3 = qpow(inv2, i); // 1/(2^i) = (inv2)^i ll term4 = pow_m[n - 2*i]; // m^(n-2i) f[i] = term1 * term2 % MOD * term3 % MOD * term4 % MOD; } // 2. 二项式反演计算 g(k) for (int k = 0; k <= m; ++k) { g[k] = 0; for (int i = k; i <= m; ++i) { ll sign = ((i - k) & 1) ? MOD - 1 : 1; // (-1)^(i-k) ll comb = C[i][k]; // C(i, k) ll term = sign * comb % MOD * f[i] % MOD; g[k] = (g[k] + term) % MOD; } } // 3. 输出结果 for (int k = 0; k <= m; ++k) { cout << g[k] << (k == m ? '\n' : ' '); } return 0; }

关键点解析与避坑指南：

1. 模运算下的除法：公式中有 ( \frac{(2i)!}{2^i} )，在模 ( MOD ) 下计算时，不能直接做除法。我们需要计算 ( 2 ) 在模 ( MOD ) 下的逆元 ( inv2 )，然后用 ( (2i)! \times (inv2)^i ) 来计算。这是模运算的基本功。
2. 组合数的预处理：本题需要多次使用组合数 ( \binom{m}{i} ) 和 ( \binom{i}{k} )，范围都在5000以内。使用递推公式 ( C[i][j] = C[i-1][j-1] + C[i-1][j] ) 进行预处理是最稳妥高效的方式。也可以使用阶乘和逆元阶乘来求，但直接递推更直观。
3. 数组大小：注意计算 ( (2i)! ) 时，( i ) 最大为 ( m )，所以需要预处理到 ( 2m ) 的阶乘。数组fac和invfac的大小应至少为 ( 2*m+5 )。
4. 边界条件：在计算 ( f(i) ) 时，必须判断 ( n \ge 2i )，否则从n个球中无法拿出 ( 2i ) 个球来满足钦定盒子的最低要求，此时 ( f(i) = 0 )。
5. 时间复杂度：双重循环计算 ( g(k) ) 是 ( O(m^2) ) 的。对于 ( m=5000 )，循环次数是2500万，在现代CPU上配合简单的模运算，通常可以在1秒内完成。如果 ( m ) 更大（如1e5），则需要使用FFT/NTT将反演优化到 ( O(m \log m) )，这涉及到生成函数，是更进阶的内容。

5. 常见问题、变体与排查技巧

在实际应用二项式反演时，会遇到各种疑问和陷阱。这里总结一份“避坑指南”。

5.1 如何判断一个问题是否能用二项式反演？

可以问自己三个问题：

1. 是否存在两种计数？一种是带“至少”或“至多”条件的（设为 ( f(n) )），另一种是带“恰好”条件的（设为 ( g(n) )）。
2. 这两种计数之间是否存在线性关系？即，一个“恰好为 ( i ) ”的方案，在计算“至少为 ( n ) ”时，是否被计算了 ( \binom{i}{n} ) 次（或类似的二项式系数次）？这是最核心的检验标准。你必须能清晰地解释为什么系数是二项式系数。
3. ( f(n) ) 是否比 ( g(n) ) 显著更容易计算？如果计算 ( f(n) ) 和 ( g(n) ) 的难度差不多，那反演就失去了意义。

如果以上三个问题的答案都是“是”，那么这个问题就非常适合使用二项式反演。

5.2 系数不是标准的 ( \binom{i}{n} ) 怎么办？

有时你会发现关系是 ( f(n) = \sum_{i=n}^{m} a(i, n) g(i) )，其中 ( a(i, n) ) 不是 ( \binom{i}{n} )。这时，经典的二项式反演公式可能不直接适用。你需要：

1. 尝试变形：看看能否通过代数变形（如提取公因子、变量替换）将 ( a(i, n) ) 化成 ( \binom{i}{n} ) 乘以某个只与 ( i ) 或 ( n ) 有关的函数。如果可以，有时能通过设新的辅助函数 ( g'(i) = h(i)g(i) ) 来转化为标准形式。
2. 使用广义反演：如果 ( a(i, n) ) 具有某种良好的性质（比如是下三角矩阵且对角线元素不为0），理论上总是存在一个逆矩阵，可以通过高斯消元法在 ( O(n^3) ) 内求解 ( g )。但这失去了二项式反演简洁性的优势。
3. 检查建模是否正确：很多时候系数不对，是因为对“至少”或“至多”的定义有偏差，或者重复计数的次数算错了。回到组合意义的源头重新审视。

5.3 反演结果出现负数或明显不对怎么办？

在模运算下，结果应该是非负的。如果出现负数（在C++中可能是很大的正数，因为取了模），或者结果明显不符合常理（比如方案数大于总排列数），请按以下步骤排查：

1. 验证 ( f(n) ) 的计算公式：这是错误的源头。用小的 ( n, m ) （比如n=4, m=2）暴力枚举所有方案，手动计算 ( f(0), f(1) ) 和 ( g(0), g(1) )，看你的计算公式是否与暴力结果一致。这是最有效的调试方法。
2. 检查模运算：确保所有乘法、加法都及时取模，特别是涉及减法时，加上MOD再取模以避免负数。检查除法是否正确地用乘法逆元替代。
3. 检查循环边界：在反演求和for (int i=k; i<=m; ++i)中，确保上界m是正确的，并且 ( f(i) ) 在i超出范围时值为0（比如我们例子中2*i > n时f[i]=0）。
4. 检查符号 ( (-1)^{i-k} )：这是最容易写错的地方。确保指数是i-k而不是k-i。可以用((i-k) & 1) ? MOD-1 : 1来判断。

5.4 二项式反演与容斥原理是什么关系？

二项式反演是容斥原理的一种简洁的代数表达形式。从容斥原理的角度看，“恰好有k个”可以表示为： [ g(k) = \sum_{j=k}^{m} (-1)^{j-k} \binom{j}{k} \sum_{|T|=j} \text{(满足T中所有条件的方案数)} ] 而这里的“满足T中所有条件的方案数”之和，恰恰就是我们的 ( f(j) )（如果“条件”定义为“某个盒子溢出”的话）。所以，二项式反演把容斥原理中需要枚举集合、求和的过程，打包成了一个简洁的公式。学会二项式反演，相当于掌握了一种“快捷键”，可以快速写出容斥的最终表达式，而不用每次都从头推导复杂的容斥系数。

5.5 有没有更快的计算方法？( O(m^2) ) 太慢了

对于 ( m ) 高达 ( 10^5 ) 的情况，( O(m^2) ) 的朴素反演是不可接受的。此时需要利用卷积进行优化。

观察反演公式： [ g(k) = \sum_{i=k}^{m} (-1)^{i-k} \binom{i}{k} f(i) = \frac{1}{k!} \sum_{i=k}^{m} \frac{(-1)^{i-k}}{(i-k)!} \cdot [i! f(i)] ] 令 ( A_i = i! \cdot f(i) )，( B_j = \frac{(-1)^j}{j!} )。则上式可以写成： [ k! \cdot g(k) = \sum_{i=k}^{m} A_i \cdot B_{i-k} ] 这正是一个减法卷积的形式。令 ( C_k = k! \cdot g(k) )，则 ( C ) 是序列 ( A ) 和 ( B ) 的卷积。具体地，( C_k = \sum_{i=0}^{m} A_{i+k} B_i )。这可以通过反转序列 ( A ) 或 ( B ) 后，使用FFT（快速傅里叶变换）或NTT（数论变换）在 ( O(m \log m) ) 的时间内计算出所有 ( C_k )，进而得到 ( g(k) )。

实操心得：在算法竞赛中，如果 ( m \leq 5000 )，用 ( O(m^2) ) 的朴素方法编码快速，不易出错。如果 ( m \leq 10^5 )，就必须掌握NTT优化卷积的方法。这要求你对生成函数和多项式运算有一定的了解。一个常见的技巧是，将二项式反演公式写成卷积形式后，其实就是多项式乘法，很多数学库（如Python的NumPy/SciPy）或竞赛模板都提供了FFT的实现。