上周复盘某场高校程序设计竞赛，翻到了D题“扔硬币”。这道题卡了不少选手，倒不是思路多难，而是只要你没把“组合数取模”和“逆元”这两个基本功吃透，写出来的代码要么暴long long，要么在取模上翻车。题面很直白：有n枚完全相同的硬币，抛掷后恰好有m枚正面朝上，求这个概率对一个大质数取模的结果。
这道题的价值在于它是一个“模板全家桶”：组合数、阶乘预处理、费马小定理求逆元、快速幂、模意义下的除法，全都在一道题里串起来了。适合刚学完数论基础、准备刷组合计数的同学，也适合比赛前拿来回扫一遍模板熟练度。整套题做下来，你对“为什么组合数取模要先预处理阶乘逆元”这个问题，会有比背模板深得多的理解。
1. 题目拆解：为什么一道概率题最后会落到组合数上
1.1 从题意到数学模型的转换
先描述一下这题的典型设定（不同赛题只是包装不同，核心几乎一致）：你抛n枚质地均匀的硬币，问恰好有m枚正面朝上的概率是多少，n和m通常是1e5甚至1e6级别，要求结果对某个大质数取模。
看到这个数据范围，第一反应就是：这题跟“模拟抛硬币”毫无关系。n这么大，逐一枚举抛掷结果铁定超时，必须直接在概率公式上做文章。n次抛硬币，每次结果独立且只有正反两种，所以总情况数是2的n次方。恰好m枚正面，本质就是从n次抛掷里选出m次“正面朝上”，这是一个典型的组合计数问题。
于是概率公式可以写成：
P = C(n, m) / 2^n
其中C(n, m)是组合数，表示“从n个位置里选m个”的方案数。到这里题目已经从“随机过程”变成了“数学计算”：算一个组合数，再算一个2的幂，最后做一次除法。
1.2 为什么要取模而不是输出小数
可能有人会问，为什么不能直接输出浮点数概率？因为n到1e6这种规模时，C(n, m)和2^n都是天文数字，直接算double早就爆精度了。更重要的是，大多数算法竞赛不允许输出浮点误差，而是要求输出最简分数在模意义下的值，也就是“把分母乘过去”变成整数。
这就引出了本题的核心难点：需要算一个类似于“a / b mod mod”的表达式。在整数取模世界里，并没有直接做除法的操作。你想算“a除以b再取模”，不能先用浮点数算商再取模，只能把除法转化成乘法——乘上b的逆元。所谓逆元，就是找一个整数x，使得b乘x在模mod下等于1。有了x之后，“a除以b”就等价于“a乘以x再取模”。
1.3 这道题到底在考什么
从出题角度来说，D题放这道题的目的是考察选手对“模运算工具箱”的熟练程度。你需要一口气完成以下动作：
- 把概率公式转成组合数除以幂的形式。
- 用阶乘预处理组合数，而不是实时算阶乘。
- 用费马小定理求分母的逆元。
- 用快速幂算2的n次方以及它的逆元。
任何一步掉链子，哪怕只是忘记对阶乘数组取模，结果都会炸。这也是为什么这题适合作为“数论入门综合检测题”——它不考你偏难怪的定理，而是考你基础数论操作能不能在高压环境下不犯错。
2. 组合数与阶乘预处理：别在循环里算阶乘
2.1 组合数的公式与朴素算法的局限
组合数C(n, m)的计算公式有两个常见形态：
C(n, m) = n! / (m! * (n-m)!)
如果你对每个询问都从头开始算阶乘，复杂度是O(n)，当n为1e6且询问很多时，整体复杂度就可能变成O(n * q)，直接超时。竞赛里标准做法是“一劳永逸”：先把0到n的所有阶乘算好存进数组，再把它们的逆元也预处理出来，之后每个C(n, m)都可以用O(1)时间查询。
为什么能O(1)查询？因为C(n, m)被拆成了三个已知数的乘除：fact[n]乘上invfact[m]再乘上invfact[n-m]。只要fact和invfact两个数组都提前准备好，组合数就是一个乘法表达式而已。
2.2 阶乘与阶乘逆元的预处理流程
阶乘部分没有太多悬念，一个循环搞定：
fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i-1] * i % MOD; }真正需要动点脑筋的是阶乘逆元。第一种做法是：先算最大的fact[n]的逆元，再倒着推回去。因为fact[n]的逆元乘以n，就等于fact[n-1]的逆元。这个递推关系看起来神奇，拆开看其实很简单：
invfact[n] = inv(fact[n]) invfact[n-1] = inv(fact[n-1]) = inv(fact[n] / n) = inv(fact[n]) * n = invfact[n] * n
所以倒着循环一遍就行：
invfact[n] = modPow(fact[n], MOD - 2); for (int i = n; i >= 1; i--) { invfact[i-1] = invfact[i] * i % MOD; }这样预处理的时间复杂度是O(n + log MOD)，比每个数都单独求逆元要快得多。很多初学者犯的错是：在循环里对每个i都调用一次快速幂求fact[i]的逆元，虽然也能对，但复杂度多了个log，大n下性能会明显变差。既然有O(n)递推的写法，就尽量别用傻办法。
2.3 C(n, m)的O(1)查询实现
预处理完成后，求组合数的函数可以写得非常干净：
long long C(int n, int m) { if (m < 0 || m > n) return 0; return fact[n] * invfact[m] % MOD * invfact[n-m] % MOD; }注意那个边界判断：m小于0或者大于n时直接返回0。这个判断在本题里也许不触发，但在更复杂的组合计数题里很容易漏掉，漏了以后数组越界或者返回一个垃圾值，你排查半天都找不到原因。
这里还有一个容易踩的坑：虽然公式是“除以m的阶乘再除以(n-m)的阶乘”，但你在代码里千万不要真的写除法。每一步乘法都要取模，乘完三个数后结果最多是1e9+7数量级的平方再取模，所以用long long存中间结果，不能用int。这可是老生常谈，但每场比赛都有人在这上面交学费。
3. 逆元原理：模意义下的“除法”是怎么实现的
3.1 逆元的定义与费马小定理的适用前提
逆元的存在意义，一句话总结就是：把除法从实数域“搬运”到模整数域。对于正整数b和模数mod，如果b与mod互质，那么一定存在一个整数x，使得：
b * x ≡ 1 (mod mod)
这个x就是b模mod的逆元。在模数是大质数（比如常用的1e9+7）时，所有1到mod-1的数都与mod互质，所以每个非零元素都有逆元。
求逆元的方法有好几种：扩展欧几里得、费马小定理、线性递推。本题最适合用的是费马小定理，因为模数是质数。费马小定理说：如果p是质数且a不是p的倍数，那么a的(p-1)次方模p等于1。也就是说：
a^(p-1) ≡ 1 (mod p)
那么a的逆元就是a^(p-2)，因为：
a * a^(p-2) = a^(p-1) ≡ 1 (mod p)
于是求逆元就变成了一个快速幂问题。很多新手对“为什么指数是MOD-2”感到困惑，其实你只要记住费马小定理右边是1，想让左边变成“a乘以某个数等于1”，那个“某个数”自然就是a^(p-2)。
3.2 快速幂实现与复杂度分析
快速幂的递归版本和迭代版本，本质都是把指数拆成二进制位来加速。迭代版本写起来最稳：
long long modPow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; }这里要特别注意：每乘一次都必须取模，不然第一步平方就把long long撑爆了。1e9+7的平方大约是1e18，恰好接近long long上界9.22e18，所以单次乘法后取模是安全的。如果模数更大或者底数更大，可能还需要用快速乘来避免溢出，但本题用不到。
调用方式很简单：
long long inverseTwoPow = modPow(modPow(2, n), MOD - 2);不过更高效的做法是只做一次快速幂：直接对2^n这个整体求逆元，也就是modPow(2, n * (MOD - 2) % (MOD - 1))。这里涉及指数对MOD-1取模的细节。根据费马小定理的推广，a的指数可以模MOD-1，因为a^(MOD-1) ≡ 1。所以：
inv(2^n) = (2^n)^(MOD-2) = 2^(n * (MOD-2) mod (MOD-1))
这样只用一次快速幂就能拿到分母逆元。两种写法都行，但理解了第二种写法，你才算真正理解了指数循环节的本质。
3.3 预处理逆元数组的另一种方法：线性递推
除了阶乘逆元的倒序递推，逆元本身还有一个线性递推公式，可以O(n)求出1到n每个数的逆元：
inv[1] = 1; for (int i = 2; i <= n; i++) { inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; }这个公式在很多组合计数题里很实用。不过本题只需要阶乘逆元，不一定需要全量逆元数组。但了解它的存在是好的，因为你以后做题时，如果只是单独求某些数的逆元，用它可能比费马小定理更快。比赛时建议把这两种模板都背熟，根据不同场景选择。
关于逆元的理解，我见过最形象的类比是：在实数里，a除以b等于a乘以b的倒数（1/b）。在模世界里，“倒数”就是逆元。你算不出来“b分之一”是多少，但是你能找到一个整数x，让b*x等于1。于是所有需要除以b的地方，都替换成乘以x。这就是“模意义下的除法”的完整逻辑。
4. 完整实现：从公式到可AC代码的最后一公里
4.1 完整代码
下面给出本题的一个可直接套用的C++实现。以n次抛硬币、恰好m次正面朝上为例，模数取1e9+7。
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; long long modPow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n, m; cin >> n >> m; vector<long long> fact(n + 1), invfact(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i-1] * i % MOD; } invfact[n] = modPow(fact[n], MOD - 2); for (int i = n; i >= 1; i--) { invfact[i-1] = invfact[i] * i % MOD; } auto C = [&](long long N, long long M) -> long long { if (M < 0 || M > N) return 0; return fact[N] * invfact[M] % MOD * invfact[N-M] % MOD; }; long long comb = C(n, m); long long total = modPow(2, n); long long ans = comb * modPow(total, MOD - 2) % MOD; cout << ans << '\n'; return 0; }4.2 关键步骤逐行讲解
整个代码的精髓全在两个数组的预处理上。先求所有阶乘，再求最后一个阶乘的逆元，然后倒推回全部阶乘逆元。这个倒推为什么是对的？因为invfact[i]就是从1乘到i的乘积的逆元，而invfact[i-1]应当是从1乘到i-1的乘积的逆元。后者等于前者的逆元乘以i——这是逆元运算和乘法交换顺序的结果。
很多选手把invfact递推方向写反了，写成从前往后推，结果推出来的全是错的。判断方向对不对有个简单方法：随便代入i=2验算一下。invfact[1]应该等于1的逆元也就是1。如果你从前往后推，invfact[1] = invfact[0] * 逆元(1)，看起来也能得到1，但推到后面就乱了。保险起见还是记住“由大到小倒着推”这个结论。
算分母时，我写的是modPow(total, MOD - 2)，也就是先算2^n，再对它求逆元。这等于直接求分母倒数再组装答案。如果你想把指数压到一次快速幂，也可以写：
long long ans = comb * modPow(2, n * (MOD - 2) % (MOD - 1)) % MOD;两种写法结果一致。第一种更好理解，第二种更快一点点。我建议初学阶段用第一种，把逻辑想清楚后再优化。
4.3 复杂度与空间
预处理阶乘和阶乘逆元的复杂度都是O(n)，一次快速幂是O(log MOD)。所以总复杂度O(n + log MOD)。如果题目有t组数据，且n的最大值固定，可以把fact和invfact处理到最大值，然后每组数据O(1)查询组合数。这样总复杂度变成O(maxN + t log MOD)。
空间上需要两个长度为n+1的long long数组。n到1e6时，大概是16MB内存，一般题目限制都够。如果n到了1e7，这个方案就会紧张，可以考虑一边算一边组合，或者用线性筛求逆元的方式优化内存，不过竞赛里很少需要这么极端的优化。
这里我还想补充一个细节：n和m都用long long读入。虽然组合数本身的n通常不超过1e6，但费马小定理的指数运算可能涉及大数乘法，用long long能保证中间不溢出。如果你用int读入，后续强制转换时一不小心就会出问题。
5. 现场排错实录：这道题最容易翻车的四个细节
5.1 逆元乘错位置：把分母逆元乘到了阶乘环节上
我在帮某位选手调这道题时，看到他把代码写成这样：
long long comb = C(n, m) * modPow(2, MOD - 2) % MOD; // 错误示例乍一看好像没问题，但仔细一算就发现，他求的是“C(n,m)除以2”而不是“C(n,m)除以2^n”。分母是2^n，不是2！如果n很小，比如n=3，这个错误几乎看不出来，一旦n变大，结果就完全不对了。正确做法是对2^n整体取逆元，也就是modPow(2, n)之后再用费马小定理求逆，或者用指数压缩的写法直接modPow(2, n * (MOD - 2) % (MOD - 1))。
5.2 n和m达到上界时数组越界
当m等于n时，C(n, n)应该等于1。此时invfact[n-m]就是invfact[0]，所以invfact[0]必须被正确初始化为1。如果你预处理invfact时从n倒推到i=1，那么invfact[0]最后会被赋值成invfact[1] * 1 = 1，没问题。但如果你初始化invfact[0]=1并且从前往后推，就容易在n-m恰好为0时取到错误值。
我建议的做法是：预处理必须保证invfact[0]=1，同时组合数函数里加m<0 || m>n的判断，双保险。这样不管边界怎么出都不会越界。
5.3 取模运算得到负数
组合数取模时，如果公式里出现了减法而你没有加MOD，中间结果可能是负数。虽然本题公式全是乘法，但你以后做别的题一定会遇到“a - b”这种模运算。到时候一定要写成((a - b) % MOD + MOD) % MOD，先加一个MOD把它抬成正数再取模。不要小看这个细节，取模为负导致的WA，属于那种报错信息都不给、只能靠对拍才能查出来的问题。
5.4 对拍验证的正确姿势
遇到这道题，建议不要只测样例，手动构造几组小数据对拍一下。比如n=1时，m=0和m=1的概率都是1/2，模1e9+7下应该输出500000004。n=2时，m=1的概率是1/2，m=0和m=2的概率都是1/4。1/4的模表示是250000002。如果这几个小数据都能对上，代码基本就稳了。
对拍的意义在于把概率已知的小数据当作测试基准。因为概率是分数，你提前算出分数的模表示，再对比代码输出，比肉眼排查更快。
6. 从这道题延伸出去：组合数取模场景的通用思路
6.1 阶乘逆元模板的复用价值
“扔硬币”这道题所用的模板，几乎可以无缝迁移到其他组合计数题里：求从n个数里选m个的方案数、求排列数、求解概率期望类题目、甚至某些容斥原理题。只要是“C(n, m)对质数取模”，预处理阶乘和逆元这个O(n)打底，之后O(1)查询的套路都是同一个。
我强烈建议你把这套模板整理成自己的“板子”，不要每次比赛手敲。因为比赛时时间紧张，手敲模板容易出错，最好是本地保存一份已经验证过的代码，需要时一分钟以内就能调出来。这道题里的fact、invfact、modPow三个组件是模板的核心，其余部分都可以按题目改。
6.2 从“除法取模”到“概率取模”的思维方式
很多新手一开始不理解“概率为什么也能取模”，觉得概率明明是0到1之间的小数。但在算法题里，概率通常被定义成“方案数除以总方案数”的比值，而方案数是整数，所以比值可以表示成“某个整数在模意义下的值”。你要做的就是把分子的方案数算出来，乘以分母方案数的逆元，就得到了概率的“模表示”。
这种思路会反复出现在各种期望题和概率DP题里。甚至很多“期望E = sum(p_i * v_i)”的题，最终也需要把每一步概率都用组合数和逆元表示出来。所以别看这道题只是问硬币概率，它教给你的“分数转模”能力，是后续刷概率期望题的基础。
6.3 对“2^n取逆元”背后的指数优化再补一刀
前面提到可以把分母逆元写成一个快速幂：modPow(2, n * (MOD - 2) % (MOD - 1))。这里用到的定理是：在模质数p下，底数非零时，指数可以模p-1进行化简。因为a^(p-1)等于1，所以a^b等于a^(b mod (p-1))。
这个优化在实际比赛中能省去一次快速幂，但第一次写的时候容易踩坑：不小心把MOD-1写成了MOD，导致指数变大，结果不变但时间复杂度多了一个量级。我自己的习惯是：除非对指数化简特别熟，否则老老实实先算2^n再求逆元，速度也不慢，正确率更高。等刷题量上来了，再逐步采用更“省事”的写法。
这道题打完之后，我把整套模板整理进了自己的本地代码库，包括阶乘预处理、逆元递推、快速幂、扩展欧几里得求逆元，一共四个模块。后来又碰到好几个组合计数题，基本都是把这套模板稍作改动直接套上去。回过头来看，这D题的难度不在于算法构思，而在于你是否能把“组合数+逆元”这套基础动作内化成肌肉记忆。最近一次直播里我也和观众强调过：把这道题的模板练到闭眼能写，省下来的时间足够你在正式比赛里多啃一道难题。
