组合数

基础定理

  1. 基本公式 : C(n,r) = n! / r!(n-r)! (从n中选r个的方案)
1
2
3
4
5
6
7
8
9
def C(n,m):
	"""
	从n个球中 选取m个球的方案数 
	"""
	res = 1
	for i in range(m):
		res = res * (n - i)
		res = res // (i + 1)
	return res
  1. 递推公式 : C(m,n) = C(m-1,n) + C(m-1,n-1)
    如果只在求答案的时候用的话 就用第一条就可以了
    但如果需要大量计算组合数 则需要对组合数进行预处理 因为求组合数事实上是在求阶乘 还是比较慢
    这个时候需要用到 递推公式

组合数预处理(递推法)

这种情况N = 1000 左右

1
2
3
4
5
6
7
8
9
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    	for (int j = 0; j <= i; j ++ )
        // 从i 个中 选取0 个的方案数 只有一种
		if (j == 0) 
			c[i][j] = 1;
		else
			// 递推公式 通常这种需要预处理的情况 值会比较大需要mod一下
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

组合数预处理(递推 + 求逆元)

这种情况 N = 100000 左右 即通过普通的递推法处理仍有可能超时

  1. 需要先预处理出所有阶乘fact[N](通常是求取模的余数 因为数会很大)
  2. 同时求出所有阶乘取模的逆元infact[N]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 通过快速来求逆元
int qmi(int a, int k, int p)    
{
    int res = 1;
    while (k > 0)
    {
        if (k & 1 == 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}