组合数模板-通用版本

简单说明

直接放代码不友好，说句话缓冲一下....这里的模板复制不会直接红一片（体验会好一些），哦，对了，使用函数C(n,m)之前，需要先用init()预处理一下，不然C(n,m)的结果就是0了。

代码区

typedef long long ll;
const ll mod = 1e9 + 7;
const int Max = 1e6 + 10;
ll fact[Max], ifact[Max];		//fact[i]是i的阶乘,ifact[i]是阶乘的除法逆元，两者用于求组合数

ll pow_mod(ll n, ll k)
{
	ll res = 1;
	n = n % mod;
	while (k > 0)
	{
		if (k & 1)
			res = res * n % mod;
		n = n * n % mod;
		k >>= 1;
	}
	return res;
}

void init()		//初始化
{
	fact[0] = ifact[0] = 1;
	for (int i = 1;i < Max; i++)
	{
		fact[i] = (fact[i - 1] * i) % mod;
		ifact[i] = pow_mod(fact[i], mod - 2);
	}
}

ll C(ll n, ll m)
{
	if (n < m || m < 0) return 0;		//不合法
	return (fact[n] * ifact[m] % mod) * ifact[n - m] % mod;
}