使用预计算阶乘计算 nCr
计算模素数的组合数
使用预计算阶乘计算 nCr 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
计算组合数
许多问题会询问从 n 个元素中选择 r 个元素有多少种方式，记作 nCr。竞赛题通常要求在素数模数下计算这个数量。🧮
阶乘公式
经典公式是：nCr 等于 n 的阶乘除以 r 的阶乘乘以 n - r 的阶乘。问题在于，模运算下不能直接做除法。
# nCr = n! / (r! * (n-r)!)阶乘会急剧增长
单个阶乘就会呈天文数字般增长，因此要对每个阶乘都取模。这能让每个值保持较小，同时保证公式在模数下仍然准确。
预先计算所有阶乘
只需构建一次阶乘数组，计算到您所需的最大 n。每个元素都等于前一个元素乘以当前下标，并在计算过程中对 p 取模。
fact[i] = fact[i-1] * i % MOD除法需要逆元
公式需要除以两个阶乘，因此您需要它们的模逆元。请记住，逆元可以将除法转换为直接的乘法。
对最大的阶乘求逆
使用费马定理和指数为 p - 2 的 pow，只需计算一次最大阶乘的逆元。这个调用就能为其余计算提供基础。
inv_fact[n] = pow(fact[n], MOD - 2, MOD)反向计算逆阶乘
通过一次从后向前的遍历，计算出其他逆阶乘；每个值都由下一个值乘以下标得到。无需额外调用幂函数。
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD组装 nCr
现在，nCr 只需计算 fact[n] 乘以 inv_fact[r]，再乘以 inv_fact[n - r]，并对 p 取模即可。每次查询只需三次查找和两次乘法。
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD每次查询都是瞬时完成
预先计算完成后，每个组合数答案都能在O(1)时间内得到。因此，当题目要求计算数千个 nCr 值时，这种模式非常有效。
处理边界情况
如果 r 为负数或大于 n，答案就是0。请先检查这个范围，以免访问阶乘数组之外的下标。
if r < 0 or r > n: return 0为数组预留充足空间
将数组大小设置为所有查询中的最大 n，再额外留出一些空间。上限过小是这里出现索引错误的常见原因。
N = 200005快速检查
预先计算完成后，一次 nCr 查询需要多长时间？
回顾
您只需预先计算一次阶乘及其逆元，之后通过三次查找即可在 O(1) 时间内回答每个 nCr 查询。注意检查 r 的范围，并确保数组足够大。🏆
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「使用预计算阶乘计算 nCr」课时是免费的吗？
是的 — 「使用预计算阶乘计算 nCr」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用预计算阶乘计算 nCr」这节课中我会学到什么？
计算模素数的组合数 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「使用预计算阶乘计算 nCr」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 在素数模数下运算
- 快速模幂运算
- 使用费马定理求模逆元
- 使用预计算阶乘计算 nCr