[组合数]求组合数的几种方法总结

转自：https://blog.csdn.net/littlewhite520/article/details/71551123

求C(n,m)%mod的方法总结

1.当n,m都很小的时候可以利用杨辉三角直接求。
C(n,m)=C(n-1,m)+C(n-1,m-1)；

2.利用乘法逆元。
乘法逆元：(a/b)%mod=a*(b^(mod-2)) mod为素数。
逆元可以利用扩展欧几里德或欧拉函数求得：

1).扩展欧几里德：b*x+p*y=1 有解，x就是所求

2).费马小定理：b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2)
1. n!/(m!*(n-m)! =x%p ,先对算出n！、m！、(n-m)!对p取模的余数，就转换为a/b=x%p;因为p为素数，所以等价于bx+py=a;然后用扩展的欧几里得定理算出 bx’+py’=1的解，x=x’*a，就得到了最终的x的值，即C(m,n)%p得值。

2.逆元 其实如果mod是素数 则b的逆元其实就是b^(mod-2)
也就是 (m!(n-m)!)的逆元为 (m!(n-m)!)p-2 ；

int inv(int a) {  
    //return fpow(a, MOD-2, MOD);  
    return a == 1 ? 1 : (long long)(MOD - MOD / a) * inv(MOD % a) % MOD;  
}  
LL C(LL n,LL m)  
{  
    if(m < 0)return 0;  
    if(n < m)return 0;  
    if(m > n-m) m = n-m;  

    LL up = 1, down = 1;  
    for(LL i = 0 ; i < m ; i ++){  
        up = up * (n-i) % MOD;  
        down = down * (i+1) % MOD;  
    }  
    return up * inv(down) % MOD;  
}  

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

3.当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算

Lucas定理：A、B是非负整数，p是质数。A B写成p进制：A=a[n]a[n-1]…a[0]，B=b[n]b[n-1]…b[0]。
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…*C(a[0],b[0]) mod p同余
即：Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p)

LL fact[maxn+5];
LL a[maxn+10];
LL inv[maxn+10];
void init(){
    a[0] = a[1] = 1;
    fact[0] = fact[1] = 1;
    inv[1] = 1;
    for(int i = 2; i <= 100005; i++)
    {
        fact[i] = fact[i-1] * i % mod;
        inv[i] = (mod - mod/i)*inv[mod%i]%mod;
        a[i] = a[i-1] * inv[i] % mod;
    }
}

LL C(int n, int m){
    return fact[n]*a[n-m]%mod*a[m]%mod;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

对了 除了lucas 还有o1 预处理逆元的方法 操作比lucas简单。lucas 主要是用于 C n m. n和m都很大的情况 只能用lucas变小

void init(){
    fact[0] = 1;
    for(int i = 1; i <= maxn; ++i)
    fact[i] = fact[i-1]*i%mod;
    inv[maxn]=quickM(fact[maxn],mod-2);
    for(int i=maxn-1;i>=0;i--)
    {
        inv[i]=inv[i+1]*(i+1);
        inv[i]%=mod;
    }
}
LL C(int n, int m){
    return ((fact[n]*inv[m])%mod*(inv[n-m]))%mod;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14