组合数

1.What’s this

CmnC_m^n 表示从m个数字里面选出n个数有多少种方式

2. Some solutions

2.1 递推求解

​ Cmn=Cm−1n+Cm−1n−1C_m^n = C_{m-1}^n + C_{m-1}^{n-1}

需要注意的是在 n=1n=1 时, Cm1=Cm−11+Cm−10C_m^1 = C_{m-1}^1 + C_{m-1}^0 ,对于选0个的我们要初始化为1

1
2
3
4
5
6
C[0][0] = 1;
for (int i = 1;i <= 10;i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

⚠️ 上面的数据范围限制在 N<1e3N < 1e3

2.2 费马小定理

往往存在一些毒瘤题目, 让你求解 1e61e6 级别的组合数

首先了解一下费马小定理 ap−1≡1(mod  p)a^{p-1} \equiv1(\mod p), 经过转换可以得到 ap−2=1a(mod  p)a^{p-2} = \frac{1}{a}(\mod p)

此时再来看一下组合式的形式 Cmn=m!(m−n)!n!C_m^n = \frac{m!}{(m-n)!n!}, 可以转换为 Cmn=inv((m−n)!)⋅inv(n!)⋅m!C_m^n = inv((m-n)!)\cdot inv(n!)\cdot m!

当时我看到这种方法后对于组合数的初始化选择的是每次调用一次快速幂进行操作,但是看到 zx 大佬的代码之后豁然开朗

先求出最后一个数的逆元, 对于前面的数,由于模的性质,直接对 inv[m+1]inv[m+1]乘以 m+1m+1, 再取模就可以得到 $ inv[m]$ 的值

1
2
3
4
f[0] = 1;
for (int i = 1;i <= n;i++) f[i] = f[i-1]*i;
inv[n] = qpow(f[n], p-2);
for (int i = n;i >= 1;i--) inv[i] = inv[i+1]*(i+1)%p;

求组合数

1
2
3
ll cnm(int n,int m) {
  	return (f[n]*inv[n]*inv[m-n])%p;
}

即开行版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
namespace CNM {
	const int N = 1e4 + 5;
	ll quick(ll x, ll n)
	{
		ll res = 1;
		while (n)
		{
			if (n & 1) res = (res*x) % mod;
			x = x * x%mod;
			n >>= 1;
		}
		return res;
	}
	ll inv(ll x) { return quick(x, mod - 2); }
	ll fac[N], invfac[N];
	void init()
	{
		fac[0] = 1;
		for (int i = 1; i < N; ++i) fac[i] = (fac[i - 1] * i) % mod;
		invfac[N - 1] = inv(fac[N - 1]);
		for (int i = N - 2; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
	}
	ll C(int n, int m)
	{
		if (n < m || m < 0) return 0;
		return fac[n] * invfac[m] % mod*invfac[n - m] % mod;
	}
}