bsp 组合数取模 转换成 strong 乘法 通过 long tex
现在目标是求 $C_n^m\%p$,p 为素数(经典 p=1e9+7)
虽然有 $C_n^m=\frac{n!}{m!(n-m)!}$,但由于取模的性质对于除法不适用,所以 $C_n^m\%p$≠$(\frac{n!\%p}{m!\%p*(n-m)!\%p} )\%p$
所以需要把 "除法" 转换成 "乘法",才能借助取模的性质在不爆 long long 的情况下计算组合数。这时候就需要用到 "逆元"!
- 逆元:对于a和p,若a*b%p≡1,则称b为a%p的逆元。
那这个逆元有什么用呢?试想一下求 $(\frac{a}{b})$%p,如果你知道 b%p 的逆元是 c,那么就可以转变成 $(\frac{a}{b})$%p = a*c%p = (a%p)(c%p)%p
那怎么求逆元呢?这时候就要引入强大的费马小定理!
- 费马小定理:对于a和素数p,满足$a ^ {
- p - 1
- }
- $ % p≡1
接着因为 $a^{p-1}$ = $a^{p-2}*a$,所以有 $a^{p-2}*a$%p≡1!对比逆元的定义可得,$a^{p-2}$ 是 a 的逆元!
所以问题就转换成求解 $a^{p-2}$,即变成求快速幂的问题了(当然这需要满足 p 为素数)。
现在总结一下求解 $C_n^m\%p$ 的步骤:
代码和另一种求法以后有空再写...
逆元 - 组合数取模
来源: http://www.bubuko.com/infodetail-2052384.html