组合数模板

1，当n,m较小,mod比较大的时候。

ll inv[maxn],fac[maxn];
void init() {
	fac[0] = 1;
	for(ll i = 1; i < maxn; i++) fac[i] = fac[i-1]*i%mod;
	inv[maxn-1] = power(fac[maxn-1], mod-2);
	for(ll i = maxn-2; i >= 1; i--) inv[i] = inv[i+1]*(i+1)%mod;
}
ll C(ll n, ll m) {
	if(m==0||n==m) return 1;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

2，当模数较小，n,m比较大的时候。

ll power(ll a, ll b) {
	ll res = 1, base = a;
	while(b) {
		if(b&1) res = res*base%mod;
		b = b>>1;
		base = base*base%mod;
	}
	return res;
}
//n % mod 的逆元
ll inv(ll n,ll mod){
    return power(n,mod-2,mod);
}
//求n! % mod
ll fac(ll n,ll mod){
    ll res = 1;
    for(int i=2;i<=n;i++) res = res * i % mod;
    return res;
}
//C(n, m) % mod
ll Comb(ll n,ll m, ll mod){
    if(m>n) return 0;
    return fac(n,mod) * inv(fac(m,mod),mod) % mod * inv(fac(n-m,mod),mod) % mod;
}
//卢卡斯定理,求C(n,m)%mod,且n,m,mod都很大.
ll Lucas(ll n, ll m,ll mod){
    return m ? Lucas(n/mod, m/mod, mod) * Comb(n%mod, m%mod,mod) % mod : 1;
}
// 要求mod为质数.