乘法逆元求组合数取模 (模为质数)

2019-04-14 21:06发布生成海报

站内文章 / 模拟电子

9240 0

为什么求组合数取模，可以用乘法逆元来做。 $C(n,r) = frac{n!}{r!*(n-r)!}$ 所以求组合数取模就是求 C(n,r) % mod

% mod. 对于正整数

和 p，如果有

，那么把这个同余方程中

的最小正整数解叫做 a 模 p 的逆元。即如果 a ％ p = 1

% p = 1，那么x的最小正整数解就是 a 的逆元。可以得到 $frac{a}{b}$ % M

( $a *b ^{m-2}$ ) % M; //费马小定理所以 C(n,r)

% M =

( $r!^{M-2}$ % M )

$(n-r)! ^{M-2}$ % M.

typedef long long LL;
const LL maxn(1000005), mod(1e9 + 7);
LL Jc[maxn];
void calJc()    //求maxn以内的数的阶乘
{
    Jc[0] = Jc[1] = 1;
    for(LL i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}
/*
//拓展欧几里得算法求逆元
void exgcd(LL a, LL b, LL &x, LL &y)    //拓展欧几里得算法
{
    if(!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}
LL niYuan(LL a, LL b)   //求a对b取模的逆元
{
    LL x, y;
    exgcd(a, b, x, y);
    return (x + b) % b;
}
*/
//费马小定理求逆元
LL pow(LL a, LL n, LL p)    //快速幂 a^n % p
{
    LL ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
LL niYuan(LL a, LL b)   //费马小定理求逆元
{
    return pow(a, b - 2, b);
}
LL C(LL a, LL b)    //计算C(a, b)
{
    return Jc[a] * niYuan(Jc[b], mod) % mod
        * niYuan(Jc[a - b], mod) % mod;
}

以上即为逆元求取组合数的方法，无论使用拓展欧几里得还是费马小定理，一开始求取Jc数组是的复杂度是 O(n),拓展欧几里得算法和费马小定理的复杂度均为 O(log(mod))，如果要求取m次组合数，则总的时间复杂度为 O(mn log(mod)). 转载自：https://www.zybuluo.com/ArrowLLL/note/713749

乘法逆元求组合数取模 (模为质数)

Ta的文章更多 >>

热门文章

乘法逆元 求组合数取模 (模为质数)

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

乘法逆元求组合数取模 (模为质数)

Ta的文章更多 >>