组合数求法汇总
一：递推求解
对于组合数，有此式： 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。
C n m C_{n}^{m} Cnm 可理解为 n n n 个数中选 m m m 个，不同的方案。对于第 n n n 个，可以选或不选，分别对应了 C n − 1 m − 1 C_{n-1}^{m-1} Cn−1m−1 和 C n − 1 m C_{n-1}^{m} Cn−1m 的方案，根据加法原理，令它们相加就得到了 C n m C_{n}^{m} Cnm。
此方法适用于 n n n 的范围不是很大的情况，而限制没有，即方便写高精度，也可以对任意模数取模，唯一缺点便是时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
附代码：
for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){if(j==0) C[i][j]=1;else C[i][j]=C[i-1][j]+C[i-1][j-1];}
}
二：利用公式，用逆元求解
根据组合数公式 C n m = n ! m ! ( n − m ) ! C_{n}^{m}=\frac{n!}{m!(n-m)!} Cnm=m!(n−m)!n!，在取模的意义下，除一个数等于乘它的逆元，我们就可以线性求出阶乘逆元，然后 O ( 1 ) O(1) O(1)求解组合数。
而此方法要求模数是质数，并且逆元必须存在。一般在模一个很大的质数
（例如 998244353 998244353 998244353 或 1 e 9 + 7 1e9+7 1e9+7）的情况下可以优先考虑它。
附代码：
int qpow(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}return res;
}
int C(int n,int m){if(n<m) return 0;return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void init(){fac[0]=1;int t=1e6;//1<=n<=1e6for(int i=1;i<=t;i++) fac[i]=fac[i-1]*i%mod;infac[t]=qpow(fac[t],mod-2);for(int i=t-1;i>=0;i--) infac[i]=infac[i+1]*(i+1)%mod;
}
三：Lucas定理
我们上文说了逆元求组合数需要模上一个质数，那么在模数任意的情况下如何求解？
这就需要利用 Lucas 定理来求解。
先上 Lucas 定理给出的式子： C n m ≡ C n m o d p m m o d p ∗ C n / p m / p ( m o d p ) C_{n}^{m}\equiv C_{n_{} mod_{}p}^{m_{}mod_{}p}*C_{n/p}^{m/p}(mod_{}p) Cnm≡Cnmodpmmodp∗Cn/pm/p(modp)。
由此，我们可以先预处理出 [ 1 , p ] [1,p] [1,p] 范围内的阶乘逆元，然后递归求解。另外，Lucas 定理也有适用范围，它一般适用于模数并不是很大（一般是小质数，范围在 1 e 5 1e5 1e5 左右，这个时候可以放心求解）。并且它还可以用于 n , m n,m n,m 非常大，模数非常小，的情况。
具体可看代码实现：
int Lucas(int n,int m,int p){if(m==0) return 1;return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;//C(n%p,m%p)见上文
}
附：练习
下面是一些求组合数的练习题。
Lucas 定理：
（纯模版题）
P3223 [HNOI2012] 排队：
（梦回高中数学，需要推出式子，然后高精度求）
P2822 [NOIP2016 提高组]组合数问题：
（递推+高精度求组合数，需要一定优化技巧）
P1680 奇怪的分组：
（插板法，蛮简单的）
P1655 小朋友的球：
（斯特林数，如果不知道的话很难推出来，可以学一学）