一句话理解
快速组合数：预处理 fac、ifac 后 O(1)。
为什么要学
模质数，n 在 1e6~1e7。
讲解
线性逆元或 fac[n]*inv(fac[k]*fac[n-k])。
例子
多组询问。
常见错误
- n≥MOD。要用卢卡斯。
- ifac 没算对。
第 497 课
快速计算组合数
🟠 进阶 约 10 分钟
练习 做完再看下一课
模质数且 n<MOD 时可预处理阶乘逆元 O(1) 查询组合数。
进度保存在本机浏览器里。
左右方向键也可翻课
第 497 课
快速组合数：预处理 fac、ifac 后 O(1)。
模质数，n 在 1e6~1e7。
线性逆元或 fac[n]*inv(fac[k]*fac[n-k])。
多组询问。
模质数且 n<MOD 时可预处理阶乘逆元 O(1) 查询组合数。
左右方向键也可翻课