文章首发于我的个人博客：欢迎大佬们来逛逛

对于求一个数字的组合数： C n m C_{n}^{m} Cnm​ 可以分解为这两种形式：

因此就得到了递推公式：

C n m = C n − 1 m − 1 + C n − 1 m C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m} Cnm​=Cn−1m−1​+Cn−1m​

由于需要用到二重循环，因此此方法适用的范围是： n , m < = 1 0 4 n,m //得到C(n,m)的组合数答案 return f[n]*g[m]*g[n-m]%p; }

容易得知此方法计算组合数的使用范围大概是： n , m < = 1 0 7 n,m //得到C(n,m)的组合数答案 return f[n]*g[m]*g[n-m]%p; } ... int lucas(int n,int m){ if (m==0){ return 1; } return lucas(n/p,m/p)*get(n%p,m%p)%p; }

此方法使用范围（大概）： n , m < = 1 0 18 ， p < = 1 0 6 n,m cnt+=n/p; n/=p; } return cnt; } int how(int n,int m,int p){ return get(n,p)-get(n-m,p)-get(m,p); } void mul(int s,int& len){ //高精度乘法 int t=0; for(int i=0;i C[len++]=t%10; t/=10; } } signed main(){ //求C(n,m) std::cin>>n>>m; init(); int len=1; C[0]=1; for (int i=1;i mul(x,len); } } for (int i=0;i