作为一个退役之后偶尔还在打打比赛的算法选手看到这种组合数加逆元的题还是忍不住点进去看两眼。今天正好有空把这道题的完整思路和实现细节从头到尾捋一遍。这道题表面是概率题骨子里是组合数学和数论基本功很适合作为巩固逆元、组合数取模、预处理阶乘这些基础套路的练手题。先说一下我这边的核心观点这类题目拿不到分的同学大多数不是卡在组合数学推导上而是卡在逆元求不对、阶乘预处理写挂、或者是没搞明白组合数取模的边界条件。所以这篇文章不打算只贴个代码就完事我会把每一步的推导逻辑、模运算的注意事项、以及我在比赛现场踩过的坑都摊开来讲。1. 题目到底在问什么“扔硬币”这个名字听起来很轻松好像就是算个概率。但实际上比赛里的D题很少有真正只需要高中概率知识的它大概率会和取模、组合数、大范围数据预处理绑在一起。我先根据这个标题还原一下题目的常见设定假设你手里有一枚硬币每扔一次朝上的概率是某个值很多时候是二分之一但也不排除题目会给你一个分数形式的概率比如 pa/b然后连续扔很多次问你恰好出现 k 次正面朝上的方案数除以某个模数的结果或者问正面朝上次数不少于某个阈值的方案数。为什么方案数会牵扯到组合数因为扔硬币的本质是一个二项分布问题。扔 n 次硬币每一次只有两种结果正面或者反面那么恰好出现 k 次正面的情况本质就是从这 n 次里选出 k 次作为正面剩下的自然就是反面选法总数就是 C(n,k)也就是组合数。[ C(n,k) \frac{n!}{k!(n-k)!} ]如果题目只问你方案数而且还带着取模的话那这道题的核心就变成了在模 MOD 的意义下求出 C(n,k) 的值。这里最难的不是理解组合数公式而是 n 的范围。如果 n 只有几百你完全可以用杨辉三角递推如果 n 到了 (10^6) 甚至 (10^7)就必须用阶乘预处理加逆元。而这道题既然专门在标题里写了“组合数逆元”那 n 的范围大概率不小直接递推组合数肯定会超时超内存。2. 为什么必须用逆元来求组合数很多刚开始学算法的朋友会有一个疑问C(n,k) 不是可以用循环算出来吗我每次乘一个数再除一个数不就行了思路本身没问题问题出在取模除法上。假设模数是 1e97你在计算过程中得到中间结果 (30 \div 6 5)。如果先对 30 取模得到 30然后再除以 6 得到 5这一步看似正常。但如果中间结果是 (35 \div 6) 呢35 对 1e97 取模还是 3535 除以 6 在整数除法里是 5 余 5可实际上你想要的可能是别的结果。更严重的是如果某个中间结果非常大先取模再除和先除再取模得到的结果很可能不一致。这里要插一个关键概念取模运算里没有除法。你需要把除法转换成乘法找一个数 (x)使得 (a \times x \equiv 1 \pmod{MOD})这个 (x) 就是 a 在模 MOD 下的逆元。用逆元可以把除法变成乘法[ a / b \equiv a \times inv(b) \pmod{MOD} ]生活化类比就是你在一个只能做加法和乘法的世界里想把一个数除以 5就得先找到一个“乘上之后等于没乘”的数这个数就是 5 在这个世界里的替身。听起来有点绕但代码写起来其实很直接。至于逆元的求法标题既然点出来了说明题目考察的就是最常用的费马小定理[ a^{MOD-2} \equiv inv(a) \pmod{MOD} ]前提是 MOD 必须是质数而且 a 不是 MOD 的倍数。1e97 刚好就是质数这也是为什么大部分竞赛题都爱用 1e97 当模数。3. 组合数取模的完整推导与代码实现搞清楚原理之后我们来看具体实现。求 C(n,k) 模 1e97最稳妥也最常用的一套流程分三步预处理阶乘数组 fac[i]表示 i 的阶乘对 MOD 取模。预处理阶乘逆元数组 invfac[i]表示 i 的阶乘的逆元对 MOD 取模。组合数通过公式计算[ C(n,k) fac[n] \times invfac[k] \times invfac[n-k] \bmod MOD ]关于预处理阶乘逆元有两种做法。一种是每个 i 都单独用费马小定理快速幂求逆元但这样复杂度是 O(n log MOD)当 n 大到 1e7 时会非常难受。另一种更聪明先求出 invfac[n] fac[n] 的逆元然后倒着递推[ invfac[i] invfac[i1] \times (i1) \bmod MOD ]理解起来也很容易因为 (fac[i1] fac[i] \times (i1))所以两边取逆元就得到上面那个递推式。这样一来只做一次快速幂剩下的都是 O(1) 的乘法整体复杂度降到 O(n)。下面给出一个完整的 C 实现这个代码风格是竞赛选手惯用的写法直接照着敲就能用#include bits/stdc.h using namespace std; typedef long long ll; const int MOD 1e9 7; const int MAXN 1000005; ll fac[MAXN], invfac[MAXN]; 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; } void init(int n) { fac[0] 1; for (int i 1; i n; i) { fac[i] fac[i - 1] * i % MOD; } invfac[n] qpow(fac[n], MOD - 2); for (int i n - 1; i 0; i--) { invfac[i] invfac[i 1] * (i 1) % MOD; } } ll C(int n, int k) { if (k 0 || k n) return 0; return fac[n] * invfac[k] % MOD * invfac[n - k] % MOD; } int main() { int n, k; cin n k; init(n); cout C(n, k) endl; return 0; }这段代码里有一个很容易被忽略的点invfac[i] invfac[i 1] * (i 1) % MOD这行为什么要乘 i1 而不是乘别的我从数学角度解释一下。(invfac[i1]) 表示 ((i1)!) 的逆元也就是 (1/(i1)!)。而 (1/i!) 等于 (1/(i1)! \times (i1))所以乘的就是 i1。这个推导我当时第一次接触时也绕了一下建议你自己在草稿纸上把阶乘展开写一遍印象会深很多。4. 题目完整推导与场景还原如果只是求一个单独的 C(n,k)其实不足以撑起D题的复杂度。竞赛里的D题往往会给多组询问。我先按多组询问的场景把完整流程讲一遍也算是对题目出现形式的一种还原。假设题目描述为给定 n 和 k问连续抛掷 n 次硬币恰好出现 k 次小头朝上的情况有多少种对 1e97 取模。其中 n 和 k 的规模是 (10^5) 以下询问次数 T 最多也是 (10^5)。这个场景下关键不是怎么求单个组合数而是怎么高效处理所有询问。最笨的办法是每组询问都重新预处理阶乘数组那复杂度直接爆炸。正确做法是一次性预处理到所有询问里最大的 n后面每组询问都是 O(1) 查询。代码结构大概是这样int main() { int T; cin T; vectorpairint, int queries(T); int maxn 0; for (int i 0; i T; i) { int n, k; cin n k; queries[i] {n, k}; maxn max(maxn, n); } init(maxn); for (auto q : queries) { cout C(q.first, q.second) endl; } return 0; }这个优化非常关键。很多同学不是不会写组合数而是没意识到预处理应该针对最大的 n而不是每组询问都重复预处理一遍。这就像你去食堂打饭明明菜已经做好了每次打饭都非要重新洗菜切菜下锅浪费时间不说还容易被后面的同学嫌弃。如果题目进一步升级比如问的是“至少出现 k 次正面”的方案数那也不复杂答案就是所有满足条件的情况求和[ \sum_{ik}^{n} C(n,i) ]这个求和如果暴力做是 O(n) 的在多组询问下可能会超时那就需要二次预处理前缀和数组 pre[i] pre[i-1] C(maxn, i)把查询复杂度降到 O(1)。但这是后话具体要不要做取决于题目给的约束条件。5. 逆元的本质和另一种求法费马小定理并不是求逆元的唯一方法但在竞赛里基本够用了。不过我还是想提一下扩展欧几里得算法因为有时候题目给的模数不是质数费马小定理就用不了了。扩展欧几里得求逆元的原理是解一个线性同余方程[ a \times x MOD \times y 1 ]如果 gcd(a, MOD) 1这个方程一定有整数解x 就是 a 在模 MOD 下的逆元。代码也非常短ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; return a; } ll g exgcd(b, a % b, y, x); y - a / b * x; return g; } ll inv_exgcd(ll a, ll MOD) { ll x, y; ll g exgcd(a, MOD, x, y); if (g ! 1) return -1; // 不存在逆元 return (x % MOD MOD) % MOD; }这里有一个值得注意的点扩展欧几里得的返回值 x 可能是负数这在取模意义下是不合法的所以最后要调整到 [0, MOD-1] 范围内也就是(x % MOD MOD) % MOD这一步。很多初学者直接 return x然后就莫名其妙 WA 到怀疑人生。费马小定理和扩展欧几里得到底选哪个我的习惯是模数是质数首选费马小定理代码短、思维直接。模数不确定或者已知不是质数用扩展欧几里得。具体到这道题模数十有八九是 1e97所以费马小定理足够。6. 现场踩坑实录下面这部分是我最想写的也是大家在网上很难查到的实战经验。我把这些年在类似题目上遇到过的各种问题整理成一个速查表不管你是第一次做这类题还是已经写过几百次组合数取模都值得扫一眼。6.1 数组开小我见过最冤的一种 WA就是 MAXN 只开到 n 的 1e5结果题目 n 最大是 1e6。一旦访问到 fac[n]程序直接越界返回一个随机值。而且因为数组越界有时候并不会当场崩溃而是在后续运算中产生一个乱七八糟的结果特别难排查。我的建议是定义 MAXN 的时候直接在题目最大 n 的基础上加 10。不要抠那点内存竞赛里 256MB 内存开两个 1e7 的数组完全没问题。另外就是养成习惯初始化函数里传入的 n 和数组上限不要混用否则容易自我混乱。6.2 没有特判 k n组合数公式本身要求 (0 \le k \le n)。如果题目询问里出现了 k n你的 C 函数应该返回 0而不是继续用公式计算。因为当 n-k 是负数时fac[n-k] 是未定义行为取模结果毫无意义。我在 C 函数第一行就直接写上if (k 0 || k n) return 0;这行代码加上之后能省掉大量的分支判断。不要觉得这是小事在循环查询里一个负数下标就能让全部结果错掉。6.3 乘法溢出MOD 是 1e97两个数相乘大约 1e18刚好超过 int 的范围但还在 long long 范围内。所以只要中间变量用 long long 就不会出事。但我见过有人图省事用 int 存结果乘完再模int 已经溢出了模出来的结果自然不对。这个倒是好解决所有涉及乘法的变量一律 long long不要混用。6.4 逆元不存在的情况费马小定理要求 a 不是 MOD 的倍数。在组合数问题里由于 n 通常远小于 MOD所以 fac[n] 不会被 MOD 整除逆元必定存在。但如果题目改了模数或者 n 可能超过 MOD那就要格外小心了。一旦 fac[n] % MOD 0费马小定理求出来的东西就不是真正的逆元了。这种情况下你就得换卢卡斯定理之类的办法但明显超出这道题的考察范围了这里只是提一嘴防止你在别的题上踩坑。6.5 读入顺序和边界测试竞赛题有时候很坏输入的 n 和 k 顺序会故意调换比如先输入 k 再输入 n。如果你没仔细看题目直接按习惯读WA 了都找不到原因。我的习惯是每次读入完先打印一遍确认cerr n n , k k endl;交题之前再用小数据手算一遍比如 n5, k2手算 C(5,2)10如果程序输出不是 10 那就肯定有地方写错了。7. 从这道题延伸出去的常见变形7.1 概率版本如果题目不是让你求方案数而是求概率比如硬币朝上的概率是 (p a/b)问你恰好 k 次朝上的概率对 MOD 取模。这时候答案就变成了[ C(n,k) \times p^k \times (1-p)^{n-k} ]注意这里的 (p^k) 和 ((1-p)^{n-k}) 也需要在模意义下计算。p 本身是分数需要先转换成模意义下的值也就是 (p a \times inv(b) \bmod MOD)。这个转换很关键因为模运算里不能直接写小数。很多第一次接触概率取模的同学会卡在这一步其实就是把除法换成逆元的问题。7.2 至少型问题如果题目问的是“至少 k 次正面”而不是“恰好 k 次正面”那答案可以写成[ ans \sum_{ik}^{n} C(n,i) ]可以预处理后缀和来加速多组询问。这里提一个优化技巧由于组合数取模有对称性 C(n,i) C(n,n-i)你可以只算一半再翻倍减少计算量。不过刷题时我图省事一般直接前缀和搞定对称性优化留到需要卡常数的时候再用。7.3 卢卡斯定理当 n 特别大比如 n 超过 1e18而 MOD 比较小比如 1e5 左右时阶乘预处理和逆元就都不好使了因为 n! 里大概率包含 MOD 的因子逆元直接不存在。这时候需要卢卡斯定理[ C(n,k) \bmod p C(n/p, k/p) \times C(n%p, k%p) \bmod p ]递归基是 k0 时返回 1。这个定理能把大组合数拆成一系列小组合数的乘积。不过说实话这道“扔硬币”大概率用不到这一步只是作为知识扩展提一下。8. 现场比赛的策略建议最后说点时间分配和心态层面的东西。在正式比赛中遇到这种明摆着考察组合数基础知识的题我一般给自己定一个时间线前 10 分钟读完题确定是组合数取模板题还是带了额外变形的题目。如果确认是模板题直接开始敲预处理和组合数模板。第 15 分钟写完并完成小数据自测。第 20 分钟提交如果有 WA优先怀疑四个地方数组越界、kn 没有特判、乘法溢出、读入顺序。很多选手不是不会写模板而是花太多时间在怀疑人生上。模板题的意义就在于用最短的时间拿到稳定的分数不要在一道已经明确知道解法的题上反复犹豫。另外一个很重要的比赛习惯是不要临时去推逆元的费马小定理推导过程。背下来就行考场上没有时间给你从零开始推导。等你熟练掌握之后你自然会理解它为什么是 MOD-2 次方这不是死记硬背是肌肉记忆。回到这道题本身。从标题的“组合数逆元”可以看出出题人就是想考察两个基础知识点的组合应用。D 题的位置决定了它不会特别难但也不会让你白拿分。你需要做到能吃透原理、能默写代码、能处理边界情况三重关卡都过了20 分钟内拿分没有压力。这种看起来很基础的题目反而最能筛掉基本功不扎实的选手。原因很简单组合数和逆元几乎是所有概率期望题的基石连基石都写不熟练的人遇到后面带包装的难题只会更绝望。我个人觉得与其去追逐那些偏怪难的算法不如多花点时间把这些看似朴素的知识点打磨到“闭眼就能写对”的程度这场比赛打完你会有很明显的体感提升。