条件概率与组合数取模：硬币题中的乘法逆元实战解析

这两天在补某高校校内程序设计竞赛的题解，一道 D 题“扔硬币”让我印象很深。点开之前以为只是个简单概率题，实际写起来才发现它把条件概率、组合数求和、模意义下除法这三个知识点串在了一起，恰好是新手到进阶之间很有代表性的一道题。如果你最近在刷概率期望类题目，或者刚学会乘法逆元正缺一个综合练习，这篇梳理应该能帮你省掉不少弯路。

我会先把题意拆清楚，然后把条件概率从定义式一步步推到组合数公式，再给出一份完整可运行的 C++ 参考实现，最后聊聊我实际踩过的几个坑。不管是只会用浮点数硬算概率，还是能写快速幂但总在取模边界上翻车，这篇文章都兼顾到了。

1. 先把题意拆明白：这题到底在求什么概率

1.1 模型设定与三个参数

题目大致是这样一个模型：有 n 枚硬币，每一枚都是均匀硬币，正反面朝上的概率各为 1/2。现在一次性抛完，我们不知道具体结果，只知道一个条件——至少有 m 枚硬币正面朝下。要你求：在这个前提下，至少有 k 枚硬币正面朝上的概率是多少，结果对某个大质数取模。

这里一共有三个参数，n 是总的硬币数，m 是“朝下”数量的下界，k 是“朝上”数量的下界。它们的关系有点像在玩一个“双区间夹逼”的问题：如果设 X 表示正面朝上的硬币数量，那么“至少 m 枚朝下”等价于 X ≤ n - m，而“至少 k 枚朝上”等价于 X ≥ k。于是问题立刻变成了一个随机变量 X 落在区间 [k, n-m] 里的条件概率问题。

理解这个转换是整个题目的关键。很多新手容易卡在“朝下”两个字上，一看到 m 就想着用 m 去算，实际上我们需要把条件统一转换成“朝上数量 X”的形式。我当时的做法是在草稿纸上先写上两个不等式：X ≥ k 和 n - X ≥ m，然后合并得到 k ≤ X ≤ n - m。一旦写出这个区间，后面所有计数都有了解法方向。

这类模型可以类比成一个抽奖问题：所有抛硬币结果一共有 2^n 种，每一种都是等可能的。已知条件等于告诉我们“只可能在某个范围内抽奖”，我们要求的则是这个范围里又满足另一个条件的比例。概率的本质是计数，这也是为什么这道题最终能落到组合数上。

1.2 “恰好 m 枚”和“至少 m 枚”是两种难度

第一次细读题面时，我特别注意了题面到底写的是“恰好 m 枚朝下”还是“至少 m 枚朝下”。这两个词会让题目难度产生本质区别。

如果条件是“恰好 m 枚朝下”，那么正面朝上的数量就被唯一确定了，就是 n - m。这时候条件概率根本不需要什么组合数求和：如果 n - m ≥ k，答案就是 1，否则就是 0。虽然也能做，但作为竞赛题就太单薄了，也不太需要乘法逆元。

所以竞赛里常见的版本其实是“至少 m 枚朝下”，这样正面朝上数的范围变成了一个区间，分母和分子都变成多个组合数的累加，模意义下的除法也就顺理成章地出现了。我的建议是，拿到题目先圈出题目里的“恰好”还是“至少”，再看清楚朝上的目标到底是“至少 k 枚”还是“恰好 k 枚”。这种一字之差能让你多花一小时调错。

我在第 5 节会再给一个关于这两种表述的速查结论。现在先按“至少 m 枚朝下、至少 k 枚朝上”的版本继续推导。

2. 条件概率推导：从定义式到组合数公式

2.1 事件与符号约定

先定义随机变量：设 X 为 n 枚硬币中正面朝上的数量。由于每枚硬币独立且等概率，X 服从二项分布，每个具体结果（比如“第 1 枚正、第 2 枚反……”）的概率都是 1/2^n。

定义两个事件：

• 事件 B：至少有 m 枚硬币朝下，也就是 X ≤ n - m。
• 事件 A：至少有 k 枚硬币朝上，也就是 X ≥ k。

题目要求的就是条件概率 P(A | B)。根据条件概率的定义式：

P(A | B) = P(A ∩ B) / P(B)

这个公式本身很简单，难点在于把 P(B) 和 P(A ∩ B) 都翻译成组合数表达。由于所有结果等概率，事件 B 的发生概率就等于“B 包含的样本点数量”除以“总样本点数量 2^n”。分子事件同理。

先用一个简单例子帮助理解：n = 2 时，4 个结果是 正正、正反、反正、反反。事件 {X = 1} 就包含正反、反正两种，概率 2/4 = 1/2。推广到一般情况，{X = i} 这个事件包含 C(n, i) 种结果，因为我们要从 n 个硬币中选出 i 个作为正面，剩下的自动就是反面。这步是整个计数推导的基石。

2.2 分母：已知条件本身的发生概率

分母是 P(B)，也就是“至少有 m 枚硬币朝下”发生的概率。用 X 表示就是 P(X ≤ n - m)。

X 可能取 0, 1, 2, ..., n-m 这些值，且这些事件互不相交，所以概率直接相加：

P(B) = Σ_{i=0}^{n-m} P(X = i) = Σ_{i=0}^{n-m} C(n, i) / 2^n

注意这里有个隐藏边界：如果 m 大于 n，那么“至少 m 枚朝下”是不可能事件，分母为 0，条件概率没有定义。竞赛数据一般不会给这种输入，但写代码时可以防御性地输出 0。

另外，如果 m = 0，分母就是 Σ_{i=0}^{n} C(n, i) = 2^n，概率为 1，相当于没有任何额外信息。这是一种很好的边界自检场景，后面代码部分我会再提。

很多初学者这里会犯一个错误：把“至少 m 枚朝下”直接翻译成 X ≥ m，然后求 P(X ≥ m)。这是方向反了。朝下数量多，意味着朝上数量少，应该是 X ≤ n - m，而不是 X ≥ m。我建议在草稿上把“朝下数量 = n - X”这个恒等式写三遍再继续。

2.3 分子：两个条件同时成立的概率

分子是 P(A ∩ B)，即“至少 k 枚朝上”且“至少 m 枚朝下”同时发生。翻译成 X 的不等式就是：

X ≥ k 且 X ≤ n - m

所以交集事件等价于 k ≤ X ≤ n - m。这个区间能否成立，取决于 k 和 n - m 的大小关系：

• 如果 k > n - m，那么没有任何 X 能同时满足两个条件，分子为 0，最终答案就是 0。
• 如果 k ≤ n - m，分子为：

P(A ∩ B) = Σ_{i=k}^{n-m} C(n, i) / 2^n

这个区间式的写法一定要写清楚。我之前偷懒直接写 Σ_{i=k}^{n} 然后发现怎么算都不对，就是因为没有把“朝下至少 m 枚”对上界 n - m 的约束考虑进去。

很多题解会直接写分子分母公式，跳过“为什么是取交集”这一步。这里我多解释一句：条件概率的分子永远是“已知条件”和“目标事件”的交集，而不是只看目标事件本身。我们是在 B 已经发生的前提下考虑 A，所以 A 中那些不满足 B 的样本点必须被排除掉。这也是 P(A | B) 和 P(A) 最本质的区别。

2.4 化简后的答案公式与数值验证

现在把分母和分子放在一起：

P(A | B) = [ Σ_{i=k}^{n-m} C(n, i) / 2^n ] / [ Σ_{i=0}^{n-m} C(n, i) / 2^n ]

由于分子分母都有共同的因子 1/2^n，它可以约掉。最终公式非常干净：

P(A | B) = Σ_{i=k}^{n-m} C(n, i) / Σ_{i=0}^{n-m} C(n, i)

这个约分过程看起来简单，但意义很重要：条件概率把样本空间缩小到事件 B 内，所有样本点仍然等概率，因此概率变成了“B 内满足 A 的结果数”除以“B 内的总结果数”。2^n 这个全局分母在条件化之后不再出现，代码里也不需要计算 2^n 的模逆元。

为了确认公式没推错，我拿一个特别小的数据手算过。设 n = 5, m = 2, k = 3，也就是说抛 5 枚硬币，已知至少 2 枚朝下，求至少 3 枚朝上的概率。

• 事件 B：X ≤ 3，包含 X = 0, 1, 2, 3，数量是 C(5,0) + C(5,1) + C(5,2) + C(5,3) = 1 + 5 + 10 + 10 = 26，即 26/32。
• 事件 A ∩ B：3 ≤ X ≤ 3，只有 X = 3，数量是 C(5,3) = 10，即 10/32。
• 条件概率 = 10/32 ÷ 26/32 = 10/26 = 5/13。

拿这个结果做后期验证非常方便，因为 n 很小时可以直接枚举所有 32 种情况，数一数满足条件的个数，不可能出错。

3. 模运算下的除法：乘法逆元是怎么来的

3.1 概率是分数，但题目只要模意义下的结果

上面推导出的答案是一个有理数，比如 5/13。但 ACM 风格的题目通常要求输出“答案对 10^9+7 取模”。直接输出浮点数是不行的，因为浮点数既不符合取模运算的定义，还可能因为精度问题在小数第 9 位之后出错。

这里必须先想清楚“一个有理数对质数取模”到底是什么意思。它指的是：如果有理数 a/b，在模 p 意义下的结果等于 a 乘以 b 在模 p 意义下的逆元，再取模，即 a × b^{-1} mod p。其中 b^{-1} 是一个整数，满足 b × b^{-1} ≡ 1 (mod p)。

可以打个比方：普通除法是“把东西平均分成 b 份”，但模世界里我们不懂什么叫“平均分”。我们只懂乘法，于是要找一个替代品 b^{-1}，让“除以 b”变成“乘上 b^{-1}”。只要 b 与模数互质，这个替代品就存在。

在整数里，5 ÷ 13 没法写成整数；但在模 10^9+7 的世界里，13 有一个对应的“乘法意义上的倒数”，乘上它之后效果和除以 13 一致。这正是乘法逆元存在的意义。

3.2 费马小定理与快速幂求逆元

模数取 10^9+7 是个大质数，这时候求逆元有非常简单的公式：费马小定理告诉我们，如果 p 是质数且 b 不是 p 的倍数，那么 b^{p-1} ≡ 1 (mod p)。两边同时除以 b，就得到 b^{p-2} ≡ b^{-1} (mod p)。

所以求 b 的逆元，本质上就是算 b^{p-2} mod p。这个幂次高达 10^9+5，必须用快速幂在 O(log p) 时间内完成。核心代码很简短：

long long mod_pow(long long a, long long b, long long mod) { long long res = 1; a %= mod; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } long long inv(long long x, long long mod) { return mod_pow(x, mod - 2, mod); }

我写快速幂时有一个习惯：先把 a 取一次模，循环里每步乘法都用 long long 接收，避免两个接近 10^9 的数相乘溢出 int。很多新手在把指数错写为 int 导致负数移位上翻过车，指数变量一定要用 long long。

还有一个容易忽略的前提：只有分母与模数互质时才存在逆元。如果分母算出来恰好是模数的倍数，那么这个公式不成立，题目一般会通过数据范围规避这种情况。实践中如果发现自己对某个用例输出异常，要检查是否触发了这个边界。

3.3 预处理阶乘与组合数，O(n) 内得到分子分母

现在公式里需要大量计算组合数 C(n, i)。如果每次都按定义算阶乘再求逆元，单次是 O(n)，整体复杂度会变得很难看。高手的做法是预处理阶乘和阶乘逆元。

设 fact[i] = i! mod p，invfact[i] = (i!)^{-1} mod p，那么：

C(n, i) = fact[n] × invfact[i] × invfact[n-i] mod p

预处理过程是先正着算 fact，再计算出 invfact[n]，然后倒着推出 invfact[i-1] = invfact[i] × i mod p。这个倒推关系来自 (i-1)! × i = i!，两边取逆元即可。完整模板：

const int MAXN = 100000; vector<long long> fact(MAXN + 1), invfact(MAXN + 1); fact[0] = 1; for (int i = 1; i <= MAXN; i++) { fact[i] = fact[i - 1] * i % MOD; } invfact[MAXN] = inv(fact[MAXN], MOD); for (int i = MAXN; i >= 1; i--) { invfact[i - 1] = invfact[i] * i % MOD; } auto C = [&](int n, int k) -> long long { if (k < 0 || k > n) return 0; return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD; };

预处理好之后，每个组合数都是 O(1) 查询。剩下的分子分母就是对一个区间求和，单次询问的复杂度 O(n)，一般够用。如果有多组询问且 n 都很大，可以用前缀和优化，我放到下一节详细说。

4. 完整代码实现与复杂度分析

4.1 可直接运行的 C++17 参考代码

把上面所有内容整合起来，我给出完整的参考实现。代码支持多组测试数据，每组输入 n、m、k，输出条件概率对 10^9+7 取模的结果。

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007LL; ll mod_pow(ll a, ll b) { a %= MOD; if (a < 0) a += MOD; ll res = 1; while (b > 0) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } ll inv(ll x) { return mod_pow(x, MOD - 2); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (!(cin >> T)) return 0; int MAXN = 100000; // 根据题目的 n 上限调整 vector<ll> fact(MAXN + 1), invfact(MAXN + 1); fact[0] = 1; for (int i = 1; i <= MAXN; i++) { fact[i] = fact[i - 1] * i % MOD; } invfact[MAXN] = inv(fact[MAXN]); for (int i = MAXN; i >= 1; i--) { invfact[i - 1] = invfact[i] * i % MOD; } auto C = [&](int n, int k) -> ll { if (k < 0 || k > n) return 0; return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD; }; while (T--) { int n, m, k; cin >> n >> m >> k; // 事件 B：至少 m 枚朝下，即 X <= n - m if (m > n) { cout << 0 << '\n'; continue; } int R = n - m; // 正面朝上数量的上界 // A ∩ B：k <= X <= R if (k > R) { cout << 0 << '\n'; continue; } ll numerator = 0, denominator = 0; for (int i = 0; i <= R; i++) { ll cur = C(n, i); denominator = (denominator + cur) % MOD; if (i >= k) { numerator = (numerator + cur) % MOD; } } cout << numerator * inv(denominator) % MOD << '\n'; } return 0; }

这份代码的核心逻辑和推导完全一一对应：先算分母也就是事件 B 的计数总和，再算分子也就是交集区间的计数总和，最后乘分母逆元。我没有把 k > R 的特判删掉，虽然循环里自动会让 numerator 等于 0，但显式判断让意图更清楚，也避免无意义的循环。

4.2 为什么这么写：边界条件与取模细节

第一个需要说明的边界是 m > n。此时“至少 m 枚朝下”是一个不可能事件，分母为 0，条件概率在数学上没有定义。题目数据一般不会给出这种情况，但作为程序必须做出处理。我选择输出 0 作为一种安全行为，同时注释写清楚原因。

第二个边界是 k > R。这种情况下事件 A 和事件 B 的交集是空集，分子为 0，最终答案必然是 0。例如 n = 5, m = 2, k = 4，已知至少 2 枚朝下等价于 X ≤ 3，不可能同时有 X ≥ 4，所以答案直接是 0。

第三个容易被忽略的细节是取模方向。求和过程我每一步都加了取模，防止 long long 溢出。mod 是 10^9+7，两个模内数字相乘最大约 10^18，long long 上限约 9.2×10^18，虽然放得下，但连续加和超过之后依然可能溢出。所以循环里我用了先加再取模的写法，这是对新手最友好的形式。

我自己第一次交的时候就是在 m > n 那里忘了特判，分母算出来是 0，inv(0) 调用快速幂后会返回一个无害但完全错误的结果。排查了半天才发现是数据里有 m 比 n 大的边界用例。

4.3 前缀和优化与多组数据的处理思路

上面的代码每组询问都是 O(R) 的循环。如果 T 不大，比如 1e3 以内，完全够用。但假如 T 和 n 都是 1e5 级别，O(T × n) 就会超时。常见的优化思路是前缀和：

如果所有询问的 n 相同，可以在预处理阶段直接维护 pre[i] = Σ_{j=0}^{i} C(n, j)，那么：

• denominator = pre[R]
• numerator = pre[R] - pre[k - 1]

每组询问变成 O(1)。如果 n 不同，更稳的写法是离线读入所有询问，按 n 分组处理，或者直接在每组询问中 O(n) 构建该 n 对应的 pre 数组。具体选哪种要看题目数据范围，不能一概而论。

我实际写代码时通常会保留单询问 O(n) 的版本，因为很多时候这类题的 T 很小，而且组合数 C(n, i) 的计算本身已经是 O(1)，循环累加的常数非常小。只有确认数据规模需要前缀和了，再改成离线版本，避免过早优化导致代码可读性下降。

5. 常见问题与排查实录

5.1 症状速查表

下面这个表是我刷这类概率题时总结的快速定位手册，按现象查找很省时间。

这里“答案比暴力枚举小/大”是我最常出现的错误。因为习惯上看到“至少”就写 ≥，把朝下的不等式写反了，导致整个区间翻过来，结果自然不对。

5.2 深挖三个高频翻车点

第一个高频翻车点是浮点数精度。很多新手第一反应是算概率然后用浮点输出，但这道题要的是模意义下的结果。浮点小数没法直接对应到模空间的整数，即使你四舍五入，也可能因为精度导致取模后结果差 1。正确姿势是永远走“组合数计数 + 逆元”路线，全程整数运算，只在最后乘一次逆元。

第二个高频翻车点是逆元不存在的情形。前面提过，费马小定理要求分母与模数互质。如果 n 很大（大于等于模数），某些组合数可能包含模数的因子，累加后分母有可能变成 0 的倍数。绝大多数题目会人为避免这种情况，出题时保证数据安全。但作为练习，我建议心里有个数：一旦发现某组数据答案异常，可以用暴力验证分母在模 p 下是否为 0。

第三个高频翻车点是前缀和的维度错误。有人会把 pre 开成一维全局数组，然后不同的 n 复用同一个数组。如果第一组 n = 5 建了 pre，第二组 n = 8 又拿同一数组查询，结果必然错。我自己的经验是：要么在每组内重建 pre，要么离线分组，不要试图用一个固定数组处理所有 n，除非题目保证所有 n 相同。

5.3 暴力对拍：怎么确认公式没推错

公式推导再自信，也建议用一个暴力程序对拍。对拍思路很直接：n 很小时枚举所有 2^n 种结果，统计满足条件的事件数量，得到精确的条件概率，再和代码输出对比。

以 n = 5, m = 2, k = 3 为例，枚举 32 种情况后得到 5/13。然后验证代码输出是否等于 5 × inv(13) mod MOD。对拍一次通过之后，你的公式和实现基本就稳了。这个习惯救了我很多次，尤其在概率题的边界处理上。

如果你的题面是“恰好 m 枚朝下”，对拍逻辑会变成：统计 X = n - m 与 X ≥ k 的关系，输出 0 或 1。这样的分支同样可以用暴力枚举验证。总之，遇到概率题不要嫌麻烦，小数据暴力对拍半小时，胜过调试一整晚。

最后说点个人体会

这类“概率 + 取模”的题目，最核心的并不是逆元本身，而是你怎么把自然语言翻译成事件表达式。只要把“至少 m 枚朝下”翻译成 X ≤ n - m，把“至少 k 枚朝上”翻译成 X ≥ k，后面的公式完全就是套模板。所以我拿到概率题的第一反应永远是先把事件写清楚，再用集合交并关系去套条件概率定义，最后才考虑模运算。

另外建议把阶乘、逆元、组合数、快速幂这一套封装成自己的代码模板。比赛的时候现写很容易出错，尤其是 invfact 倒推那两行，我至少写错过三次。提前准备好模板，能把宝贵的比赛时间留给真正的思考。

如果你也刚做完这道题，可以试试把条件改成“恰好 k 枚朝上”再推一遍，你会发现推导路径完全不同，正好用来检验自己是不是真的理解了区间和点的区别。这一题吃透之后，再遇到这类条件概率 + 组合计数的题，你会顺手很多。