首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

组合数

所以这里要介绍一个种新的组合算法。在了解此算法之前,要先了解一些概念。 1 同余 同余是数论中的重要概念。...试想一下(a / b)%p,如果你知道b%p的逆元是c,那么就可以转变成(a/b)%p = (a/b) * 1 % p = (a / b) * (b* c % p) % p = a*c % p = (...那怎么逆元呢?这时候就要引入强大的费马小定理!...4 快速幂 这部分的内容可以参考 小朋友学算法(6):幂pow函数的四种实现方式 中的第四种方法 (二)逆元 + 快速幂组合思路 现在目标是C(n, m) %p,p为素数(经典p=1e9+7)。...% p) (2)m! % p的逆元(即fac[m]的逆元):根据费马小定理,x%p的逆元为x^(p−2), 因此通过快速幂,求解fac[m]^(p−2) % p,记为M (3)(n-m)!

56020
领券