组合数模板

证明过程可参考此篇博客https://www.cnblogs.com/liziran/p/6804803.html

Code:

ll f[Max];
ll qpow(ll a, ll b) {
   
	ll ans = 1, base = a;
	while (b) {
   
		if (b & 1) ans = ans * base % Mod;
		base = base * base % Mod;
		b >>= 1;
	}
	return ans;
}
void init() {
   
	f[0] = 1;
	for (int i = 1;i <= 2e5;i++) {
   
		f[i] = f[i - 1] * i % Mod;
	}
}
ll cal(ll n, ll m) {
   
	if (n < m) return 0;
	return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
}