Burnling's Blog
0%

组合数

发表于 更新于

定义

  • 从 $n$ 个物品中选 $m$ 个物品的方案数。
  • 记作 $C^m_n$ 或 $C(n,m)$ 或 $\binom{n}{m}$。
  • $C_n^m=\dfrac{n!}{m!(n-m)!}$
  • $Cn^m=C{n-1}{m-1}+C_{n-1}^{m}$

性质

  1. $C^m_n=C^{n-m}_n$
  2. $Cn^m=\textstyle\sum^{n-1}{i=0}C^{m-1}_i$
  3. $m\times Cn^m=n\times C^{m-1}{n-1}$
  4. $\textstyle\sum_{i=0}^nC_n^i=2^n$

代码

莫名其妙拿了个次优解（？

利用乘法逆元快速求解 查询复杂度 $O(\log M)$ ，$M$ 为模数。

仅适用于模数为质数的情况。

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
ll QuickPow(ll a,ll b){
	ll res = 1;
	while(b){
		if(b&1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res % MOD;
}

ll fro[maxN];

inline void pre(ll n){
	fro[0] = 1;
	for(ll i = 1;i<=n;i++) fro[i] = fro[i-1] * i % MOD;
}

inline ll inv(ll n){
	return QuickPow(n,MOD-2) % MOD;
}

inline ll C(ll n,ll m){
	if(n < m) return 0;
	return fro[n] * inv(fro[m])% MOD * inv(fro[n-m]) % MOD;
}

卡特兰数

  • 简单来说，卡特兰数就是一个有规律的数列，在坐标图中可以表示为：从原点 $(0,0)$ 出发，每次向 $x$ 轴或者 $y$ 轴正方向移动 $1$ 个单位，直到到达$(n,n)$点，且在移动过程中不越过第一象限平分线的移动方案总数。

  • $Catalann=\dfrac{1}{n+1}C^n{2n}$