【概述】

组合数取模，即计算组合数 ，由于 ，取模对除法不适用，因此可以使用逆元或递推来解决这个问题。

【逆元求法】

1.要求：p 是质数 2.时间复杂度：O(n) 3.求解  的步骤： 1）通过循环，预先算好所有小于 MAXX 的阶乘（%p）的结果，存到数组 fac[] 中 (fac[i] = i!%p) 2）求 的逆元（即求fac[m]的逆元），根据费马小定理，x%p 的逆元为，通过快速幂，求解 ，记为 M 3）求  的逆元：同上，即求解  4）通过逆元计算组合数，即： 4.实现： long long n,m,p; long long fac[MAXX]; /*快速幂求x^n%mod*/ long long pow_mod(long long x, long long n, long long mod) { long long res=1; while(n) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } LL inv(LL x){ return pow_mod(x,p-2,p); } int main() { while(scanf("%lld %lld %lld", &n, &m, &p)!=EOF) { fac[0]=1; for(int i=1;i<=n;i++)//预处理求fac，fac[i] = i!%p fac[i]=fac[i-1]*i%p; /*组合数 = n!*(m!%p的逆元)*((n-m)!%p的逆元)%p */ long long res=fac[n]*inv(fac[m])%p*inv(fac[n-m])%p; printf("%lld ",res); } }

【递推】

1.要求：无 2.时间复杂度：O(n^2) 3.方法：C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m) 4.实现 int comb[N][N]; const int p=1e9+7; void init() { for(int i=0;i=p) comb[i][j]-=p; } } }