如何求组合数(逆元)

#include <iostream> //组合数
#include <cstdio>   
#include <cstring>
using namespace std;
const long long mod=1e9+7;
long long jc[1000000],ny[1000000];  //jc[i]表示i的阶乘   ny[i]表示i的阶乘的逆元

long long ksm(long long a,long long b) //快速幂a的b次
{
    long long ans=1;

    while(b>0)
    {
        if(b%2==1)ans*=a,ans%=mod;

        a*=a;
        a%=mod;
        b/=2;

    }
    return ans;

}
long long c(long long n,long long m)  //求组合数
{
    if(n==0)return 1;
    return jc[m]*ny[n]%mod*ny[m-n]%mod;  //m的阶乘*n阶乘的逆元*(m-n)阶乘的逆元
}

int main()
{
    jc[1]=1;
    ny[1]=1;
    for(int i=2;i<1000000;i++) //预处理jc数组和ny数组
    {
     jc[i]=jc[i-1]*i%mod;
     ny[i]=ksm(jc[i],mod-2);
    }
    
    
    int a,b;
    cin>>a>>b;
    cout<<c(a,b)<<endl;  ///c(n,m) = m!/n!(m-n)!
}


///a的逆元 = a的mod-2次方

大佬给讲的 自己加了一些备注

原文地址:https://www.cnblogs.com/hao-tian/p/9153401.html