引入

在做题时，经常会遇到需要计算从 \(n\) 个物品中选择 \(m\) 个的方案数的情况。
我们就需要用到计算组合数的公式：\(\large{C_m^n} = \dfrac{n!}{(n-m)!m!}\)。这篇文章里为了方便，用 \(\dbinom{n}{m}\) 代替 \(\large{C_m^n}\)。

方法

1.乘法逆元

最简单的方法莫过于用组合数公式直接求。

但在 \(21!\) 就已经爆 long long，所以通常是会有模数的。
如果有了模数，那么普通的除法肯定是会出大问题，就又要引入逆元。

如果一个线性同余方程 \(ax \equiv 1 \pmod b\) ，则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\) 。

定义 \(fact_n = n!\bmod p\) (\(p\) 为模数)，\(infact_n = (n!)^{-1}\bmod p\)。那么我们就可以把原始公式转换成 \(\dbinom{n}{m}=fact_n \cdot infact_{n-m} \cdot infact_m\)。

在这里，求乘法逆元可以用线性递推法 \(inv_i = (p-\lfloor\frac{p}{i}\rfloor)inv_{p\bmod i}\bmod p\)。

const int mod = ...;
int inv[],fact[],infact[];
void init(){
	fact[1]=infact[1]=inv[1]=1;
	for(int i=2;i<=...;i++){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		fact[i]=fact[i-1]*i%mod;
		infact[i]=infact[i-1]*inv[i]%mod;
	}
}
int C(int n,int m){
	return (ll)fact[n]*infact[n-m]%mod*infact[m]%mod;
}