求组合数C(n,m) % mod的几种方法

@[TOC]

算法一：乘法逆元，在m,n和mod比较小的情况下适用

乘法逆元：（a/b）% mod = a * b^(mod-2)，mod为素数
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define LL long long

using namespace std;

const int MOD = 9982;

LL pow(LL x)
{
    LL n = MOD-2; 
    LL res=1;
    while(n>0)
    {
       if(n & 1)    
            res=res*x%MOD;
       x=x*x%MOD;
       n>>=1;
    }
    return res%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 * pow(down) % MOD;  //乘法逆元 
}  

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    LL ans = C(n,m)%MOD; 
    printf("%lld\n",ans);
    return 0;
}

算法二：Lucas定理 + 乘法逆元，适用于mod为素数且大小为10^5左右

**Lucas定理：我们令 n = tp + r , m = sp + q .（q ，r ≤p）,那么在这里插入图片描述

即：Lucas(n,m,p)=C(n%p,m%p)Lucas(n/p,m/p,p)*

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define LL long long

using namespace std;

const int MOD = 100000;

LL pow(LL x)
{
    LL n = MOD-2; 
    LL res=1;
    while(n>0)
    {
       if(n & 1)    
            res=res*x%MOD;
       x=x*x%MOD;
       n>>=1;
    }
    return res%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 * pow(down) % MOD;  //乘法逆元 
} 


//当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算
LL Lucas(LL n, LL m)
{
    if(m == 0)    return 1;
    return C(n%MOD,m%MOD)*Lucas(n/MOD,m/MOD)%MOD;    
} 

int main()
{
    int T,n,m;
    LL ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        ans = Lucas(n,m)%MOD;
        printf("%lld\n",ans);
    } 
    return 0;
}

算法三：预处理 + 乘法逆元，适用于mod为素数且比较大的时候（超过10^5）

预处理的时候注意: m!的MOD次方 = (m-1)!的MOD次方 * m的MOD次方

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define maxn 1000000

using namespace std;

const int MOD = 998244353;

LL fact[maxn+5];    //阶乘 
LL a[maxn+10];    // 乘法逆元 
//LL inv[maxn+10];    //快速幂 

LL pow(LL x)
{
    LL n = MOD-2;
    LL res=1;
    while(n>0)
    {
       if(n%2==1)    
            res=res*x%MOD;
       x=x*x%MOD;
       n>>=1;
    }
    return res;    
}

void init(){
    a[0] = a[1] = 1;
    fact[0] = fact[1] = 1;
//  inv[1] = 1;
    for(int i = 2; i <= 1000005; i++)
    {
        fact[i] = fact[i-1] * i % MOD;
        a[i] = a[i-1] * pow(i) % MOD;    //m!的MOD次方 = (m-1)!的MOD次方 * m的MOD次方 
//      inv[i] = (MOD - MOD/i)*inv[MOD%i]%MOD;
//      a[i] = a[i-1] * inv[i] % MOD;    
    }
}

LL C(int n, int m){    //乘法逆元 
    if(n<0||m<0||n<m)return 0;
    return fact[n]*a[n-m]%MOD*a[m]%MOD;
}

int main()
{
    int T,n,m;
    LL ans;
    init();//预处理 
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        ans = C(n,m)%MOD;
        printf("%lld\n",ans);
    } 
    return 0;
}