1. 项目概述从“恰好”到“至少”的思维转换在组合数学和概率论的实际问题里我们常常会遇到两种看似相似、实则互为“镜像”的计数场景。比如统计一个班级里“恰好有3个同学获得A”的情况和统计“至少有3个同学获得A”的情况。直接计算“恰好”往往非常困难因为它要求一个精确的边界而计算“至少”则相对容易因为它可以通过容斥原理或者更简单的方法进行累积。二项式反演Binomial Inversion正是连接这两个世界的桥梁它提供了一套精确的公式让我们能够从容易计算的“至少/至多”计数结果反推出难以直接计算的“恰好”计数结果。这个工具的强大之处在于其普适性和简洁性。它不仅仅是一个数学公式更是一种重要的组合学思想。当你掌握了它再看许多复杂的包含-排除问题、错排问题甚至是一些概率期望问题会有一种豁然开朗的感觉。它把一种需要复杂分类讨论的思维过程转化为了一个可以机械套用的代数运算。无论你是正在准备算法竞赛的学生还是从事数据分析需要处理复杂计数问题的工程师理解二项式反演都能让你的工具箱里多出一件称手的利器。2. 核心原理公式、推导与直观理解2.1 两种标准形式及其互推二项式反演通常以两种对称的形式出现它们分别处理“至少”和“至多”到“恰好”的转换。形式一从“至少”反演到“恰好”这是最常见的形式。设 ( f(n) ) 表示“至少”有 ( n ) 个元素满足某种性质的方案数( g(n) ) 表示“恰好”有 ( n ) 个元素满足该性质的方案数。那么它们满足以下关系 [ f(n) \sum_{in}^{m} \binom{i}{n} g(i) \quad \text{对于所有 } n 0, 1, ..., m ] 其反演公式为 [ g(n) \sum_{in}^{m} (-1)^{i-n} \binom{i}{n} f(i) ] 这里的 ( m ) 是元素总数的上界。这个公式的直观意义是要得到“恰好n个”我们从“至少n个”中减去那些“实际上多于n个”的部分。由于“至少n个”中包含了“恰好n1个”、“恰好n2个”……的情况并且这些“恰好k个”在计算“至少n个”时被重复计算了 ( \binom{k}{n} ) 次从k个中任选n个作为那“至少”的n个所以我们需要用带符号的容斥来精确扣除。形式二从“至多”反演到“恰好”另一种对称的形式。设 ( F(n) ) 表示“至多”有 ( n ) 个元素满足性质的方案数( G(n) ) 表示“恰好”有 ( n ) 个的方案数。它们的关系是 [ F(n) \sum_{i0}^{n} \binom{n}{i} G(i) ] 其反演公式为 [ G(n) \sum_{i0}^{n} (-1)^{n-i} \binom{n}{i} F(i) ] 这两种形式本质上是等价的可以通过变量替换相互转化。通常我们根据具体问题中哪个量“至少”或“至多”更容易计算来决定使用哪一种形式。2.2 组合证明与生成函数视角理解为什么这个公式成立比记住公式更重要。这里给出一个经典的组合证明思路以形式一为例我们已知 ( f(n) \sum_{in}^{m} \binom{i}{n} g(i) )。现在将反演公式 ( g(n) \sum_{in}^{m} (-1)^{i-n} \binom{i}{n} f(i) ) 代入右边进行验证 [ \begin{aligned} \sum_{in}^{m} \binom{i}{n} g(i) \sum_{in}^{m} \binom{i}{n} \left[ \sum_{ji}^{m} (-1)^{j-i} \binom{j}{i} f(j) \right] \ \sum_{jn}^{m} f(j) \sum_{in}^{j} \binom{i}{n} \binom{j}{i} (-1)^{j-i} \ \sum_{jn}^{m} f(j) \binom{j}{n} \sum_{in}^{j} \binom{j-n}{i-n} (-1)^{j-i} \quad \text{(利用组合恒等式)} \ \sum_{jn}^{m} f(j) \binom{j}{n} \sum_{k0}^{j-n} \binom{j-n}{k} (-1)^{(j-n)-k} \quad \text{(令 k i-n)} \ \sum_{jn}^{m} f(j) \binom{j}{n} (1 - 1)^{j-n} \quad \text{(二项式定理)} \ f(n) \quad \text{(因为仅当 jn 时} (1-1)^{0}1 \text{否则为0)} \end{aligned} ] 这个证明过程清晰地展示了系数如何通过二项式定理的展开与收缩相互抵消最终只剩下我们想要的项。它体现了组合数学中一种深刻的对偶性。从生成函数的角度看二项式反演可以看作是某种变换的逆。将序列 ( {g(n)} ) 和 ( {f(n)} ) 联系起来的关系类似于一种二项式卷积。这种视角在理论研究中非常有力能够统一处理一系列相关问题。注意初次接触推导过程可能会觉得有些繁琐但不必强求每一步都立刻理解。关键是要抓住核心思想利用带符号的二项式系数进行容斥以精确分离出“恰好”的情况。在实际应用中我们更多是直接套用公式但了解其来源能让你在遇到变种问题时知道如何调整。3. 典型应用场景与建模方法二项式反演的价值在于它能将许多复杂问题化繁为简。下面通过几个经典场景看看如何将实际问题抽象成反演模型。3.1 场景一错排问题Derangement问题有 ( n ) 封信和 ( n ) 个对应的信封所有信都装错信封的方案数 ( D_n ) 是多少建模与求解定义“至少”设 ( f(k) ) 表示“至少有 ( k ) 封信装对了信封”的方案数。这很容易计算先从 ( n ) 封信中选出 ( k ) 封保证装对有 ( \binom{n}{k} ) 种选法剩下的 ( n-k ) 封信任意装有 ( (n-k)! ) 种装法。因此 ( f(k) \binom{n}{k} (n-k)! \frac{n!}{k!} )。定义“恰好”设 ( g(k) ) 表示“恰好有 ( k ) 封信装对”的方案数。我们最终要求的是 ( g(0) )即全部装错的方案数 ( D_n )。应用反演公式形式一根据关系 ( f(k) \sum_{ik}^{n} \binom{i}{k} g(i) )代入 ( k0 ) [ f(0) \sum_{i0}^{n} \binom{i}{0} g(i) \sum_{i0}^{n} g(i) ] 但 ( f(0) n! )所有信任意装。这并没有直接给出 ( g(0) )。我们需要完整的反演。 由反演公式 [ g(k) \sum_{ik}^{n} (-1)^{i-k} \binom{i}{k} f(i) \sum_{ik}^{n} (-1)^{i-k} \binom{i}{k} \frac{n!}{i!} ]计算目标令 ( k0 ) [ D_n g(0) \sum_{i0}^{n} (-1)^{i} \binom{i}{0} \frac{n!}{i!} n! \sum_{i0}^{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) )建模与求解建立关系如果“至少包含S”意味着子集必须包含S中的所有元素那么对于任意集合 ( T \supseteq S )这个子集自然也“至少包含S”。因此( F(S) ) 可以表示为所有以 ( S ) 为子集的集合 ( T ) 对应的 ( G(T) ) 之和。但这里不是简单的二项式系数因为集合大小不一。我们需要更一般的莫比乌斯反演。连接二项式反演如果我们只关心集合的大小而不是具体是哪些元素问题就简化了。设 ( f(k) ) 为“至少包含某个特定大小为 ( k ) 的集合”的子集数量由于对称性这个数与具体是哪个k元集无关。设 ( g(k) ) 为“恰好包含某个特定大小为 ( k ) 的集合”的子集数量。那么一个“恰好包含某个i元集”的子集在计算“至少包含某个k元集”时会被计数多少次呢这要求那个k元集是那个i元集的子集。从一个i元集中选出一个特定的k元子集只有1种方式如果固定了那个k元集的话。但我们的 ( f(k) ) 定义是“至少包含某个特定的k元集”所以对于每个大小为i的超集只有1个特定的k元子集符合要求。因此关系为 [ f(k) \sum_{ik}^{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} )但通过变量代换可以化为标准形式。应用与意义这个场景展示了二项式反演在更一般的集合计数问题中的核心思想通过一个容易计算的、带有“至少/至多”条件的计数函数去求解精确的计数函数。在算法竞赛中许多涉及“钦定”、“强制满足”某些条件的计数题最终都归结于这一模型。注意事项在将实际问题建模为二项式反演时最易出错的地方是确定求和系数 ( \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_{ik}^{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^97 )) 取模的结果。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) ) 容易算首先从m个盒子中钦定i 个盒子作为“溢出盒”。有 ( \binom{m}{i} ) 种钦定方式。为了保证这 i 个被钦定的盒子每个至少2个球我们可以先拿出 ( 2i ) 个球每个被钦定的盒子先分配2个球。由于球不同分配这 ( 2i ) 个球到 i 个盒子的方式数为将 ( 2i ) 个不同的球分成 i 个有序的组对应i个盒子每组恰好2个球。这个方案数是 ( \frac{(2i)!}{2^i} ) 先全排列再除以每个盒子内2个球的顺序。现在还剩下 ( n - 2i ) 个球。这 ( n-2i ) 个球可以任意分配到全部 m 个盒子中包括之前被钦定的 i 个盒子没有任何限制。每个球有 m 种选择所以方案数是 ( m^{n-2i} )。因此( 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_{ji}^{m} \binom{j}{i} g(j) ] 这正是二项式反演的标准形式一其中 ( f(i) ) 是已知的我们已推导出公式( g(j) ) 是未知的。第四步应用反演公式求解根据二项式反演公式一 [ g(k) \sum_{ik}^{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[i1] * (i1) % 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; }关键点解析与避坑指南模运算下的除法公式中有 ( \frac{(2i)!}{2^i} )在模 ( MOD ) 下计算时不能直接做除法。我们需要计算 ( 2 ) 在模 ( MOD ) 下的逆元 ( inv2 )然后用 ( (2i)! \times (inv2)^i ) 来计算。这是模运算的基本功。组合数的预处理本题需要多次使用组合数 ( \binom{m}{i} ) 和 ( \binom{i}{k} )范围都在5000以内。使用递推公式 ( C[i][j] C[i-1][j-1] C[i-1][j] ) 进行预处理是最稳妥高效的方式。也可以使用阶乘和逆元阶乘来求但直接递推更直观。数组大小注意计算 ( (2i)! ) 时( i ) 最大为 ( m )所以需要预处理到 ( 2m ) 的阶乘。数组fac和invfac的大小应至少为 ( 2*m5 )。边界条件在计算 ( f(i) ) 时必须判断 ( n \ge 2i )否则从n个球中无法拿出 ( 2i ) 个球来满足钦定盒子的最低要求此时 ( f(i) 0 )。时间复杂度双重循环计算 ( g(k) ) 是 ( O(m^2) ) 的。对于 ( m5000 )循环次数是2500万在现代CPU上配合简单的模运算通常可以在1秒内完成。如果 ( m ) 更大如1e5则需要使用FFT/NTT将反演优化到 ( O(m \log m) )这涉及到生成函数是更进阶的内容。5. 常见问题、变体与排查技巧在实际应用二项式反演时会遇到各种疑问和陷阱。这里总结一份“避坑指南”。5.1 如何判断一个问题是否能用二项式反演可以问自己三个问题是否存在两种计数一种是带“至少”或“至多”条件的设为 ( f(n) )另一种是带“恰好”条件的设为 ( g(n) )。这两种计数之间是否存在线性关系即一个“恰好为 ( i ) ”的方案在计算“至少为 ( n ) ”时是否被计算了 ( \binom{i}{n} ) 次或类似的二项式系数次这是最核心的检验标准。你必须能清晰地解释为什么系数是二项式系数。( f(n) ) 是否比 ( g(n) ) 显著更容易计算如果计算 ( f(n) ) 和 ( g(n) ) 的难度差不多那反演就失去了意义。如果以上三个问题的答案都是“是”那么这个问题就非常适合使用二项式反演。5.2 系数不是标准的 ( \binom{i}{n} ) 怎么办有时你会发现关系是 ( f(n) \sum_{in}^{m} a(i, n) g(i) )其中 ( a(i, n) ) 不是 ( \binom{i}{n} )。这时经典的二项式反演公式可能不直接适用。你需要尝试变形看看能否通过代数变形如提取公因子、变量替换将 ( a(i, n) ) 化成 ( \binom{i}{n} ) 乘以某个只与 ( i ) 或 ( n ) 有关的函数。如果可以有时能通过设新的辅助函数 ( g(i) h(i)g(i) ) 来转化为标准形式。使用广义反演如果 ( a(i, n) ) 具有某种良好的性质比如是下三角矩阵且对角线元素不为0理论上总是存在一个逆矩阵可以通过高斯消元法在 ( O(n^3) ) 内求解 ( g )。但这失去了二项式反演简洁性的优势。检查建模是否正确很多时候系数不对是因为对“至少”或“至多”的定义有偏差或者重复计数的次数算错了。回到组合意义的源头重新审视。5.3 反演结果出现负数或明显不对怎么办在模运算下结果应该是非负的。如果出现负数在C中可能是很大的正数因为取了模或者结果明显不符合常理比如方案数大于总排列数请按以下步骤排查验证 ( f(n) ) 的计算公式这是错误的源头。用小的 ( n, m ) 比如n4, m2暴力枚举所有方案手动计算 ( f(0), f(1) ) 和 ( g(0), g(1) )看你的计算公式是否与暴力结果一致。这是最有效的调试方法。检查模运算确保所有乘法、加法都及时取模特别是涉及减法时加上MOD再取模以避免负数。检查除法是否正确地用乘法逆元替代。检查循环边界在反演求和for (int ik; im; i)中确保上界m是正确的并且 ( f(i) ) 在i超出范围时值为0比如我们例子中2*i n时f[i]0。检查符号 ( (-1)^{i-k} )这是最容易写错的地方。确保指数是i-k而不是k-i。可以用((i-k) 1) ? MOD-1 : 1来判断。5.4 二项式反演与容斥原理是什么关系二项式反演是容斥原理的一种简洁的代数表达形式。从容斥原理的角度看“恰好有k个”可以表示为 [ g(k) \sum_{jk}^{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_{ik}^{m} (-1)^{i-k} \binom{i}{k} f(i) \frac{1}{k!} \sum_{ik}^{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_{ik}^{m} A_i \cdot B_{i-k} ] 这正是一个减法卷积的形式。令 ( C_k k! \cdot g(k) )则 ( C ) 是序列 ( A ) 和 ( B ) 的卷积。具体地( C_k \sum_{i0}^{m} A_{ik} 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的实现。
尧图网络