关于组合计数（知识点）

经验分享区
1

前置

为什么要有前置，好奇怪呀（好久前写的了，我为什么要写，后面我好像没用啊）

二项式定理：

(a+b)^n=\sum_{k=0}^n \dbinom{n}{k}a^{n-k}b^k,n \in \mathbb{N^*}

组合数

C(n,m):定义：n 中选 m 个又可写成 \binom{n}{m}
即

\dbinom{n}{m}=\frac{n!}{m!(n-m)!}
\therefore C(n,k)=C(n,n-k)

有性质（可从组合意义证明）

C(n+1,m)=C(n,m)+C(n,m-1)

由此可得

\sum_{i=0}^mC(i,n)=C(m+1,n+1)
\sum_{i=l}^rC(i,n)=C(r+1,n)-C(l,n)

又有性质（可从组合意义证明）

C(n,m)\times C(m,r)=C(n,r) \times C(n-r,m-r)

范德蒙德恒等式（即下标之和为定值）

\sum_{k=0}^rC(m,k) \times C(n,r-k)=C(m+n,r)

Lucas 定理
若 p 为素数，m 和 n 为非负整数,将其表示为 p 进制
k 为进制上最大数

C(m,n) \equiv \prod_{i=0}^k C(m_i,n_i)\mod p

若 n_i>m_i 则 C(m_i,n_i)=0
Lucas 定理代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
int _,n,m,p,inv[N],fac[N]={0,1};
int qpow(int x,int k,int p){
	int res = 1;
	while(k){
		if(k&1) res = (res*x)%p;
		x=(x*x)%p;
		k >>= 1;
	} 
	return res;
}
int getinv(int x,int p){
	return qpow(x,p-2,p);
}
int C(int n,int m,int p){
	if(m < n) return 0;
	if(n < p && m < p) return fac[m]*inv[n]%p*inv[m-n]%p;
	return C(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> _;
	while(_ --){
		cin >> n >> m >> p;
		for(int i = 2;i <= p;i ++){
			fac[i]=fac[i-1]*i%p;
		}
		inv[p-1] = getinv(fac[p-1],p);
		for(int i = p-1;i >= 1;i --) inv[i-1] = inv[i]*i%p;
		cout << C(n,n+m,p)%p << "\n";
	}
	return 0;
}

卡特兰数

有一个大小为 n\times n 的方格图左下角为 (0, 0) 右上角为 (n, n)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 y=x 上方（但可以触碰）的情况下到达右上角有多少可能的路径？ ——卡特兰数
对于卡特兰数 H_n，有

H_n= \binom{2n}{n} - \binom{2n}{n-1} =\frac{\binom{2n}{n}}{n+1}

容斥原理

\left| \bigcup_{i = 1}^{n} A_{i} \right| = \sum_{S \subseteq \{1, \ldots, n\}, S \neq \varnothing} (-1)^{\vert S \vert + 1} \left| \bigcap_{i \in S} A_{i} \right|

容斥原理，它用于计算多个集合的并集的元素个数。公式左边表示从 A_1 到 A_n 的并集的元素个数，右边是一个求和公式，对所有非空子集 S 进行求和，其中每一项通过 (-1)^{\vert S \vert + 1} 来调整符号，并计算子集 S 中所有集合的交集的元素个数。

二次项反演

  • 形式1（前缀）

反演前：

f(n) = \sum_{k=0}^{n} \binom{n}{k} g(k)

反演后：

g(n) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} f(k)
  • 形式2（后缀）
f(n)=\sum_{k=n}^m \binom{k}{n}g(k)(m \geq n)

反演前：

g(n)=\sum_{k=n}^m(-1)^{k-n} \binom{k}{n}f(k)

矩阵

  • 定义一：向量乘矩阵
    对于一个 1 \times n 的向量 x 和一个 n \times n 的矩阵 A，得到一个 1 \times n 的向量 y，有
y_j=\sum_{i=1}^n x_i \times A_{i,j}
  • 定义二：矩阵乘矩阵
    对于一个 n \times n 的矩阵 A 和另一个 n \times n 的矩阵 B，得到一个 n \times n 的矩阵 C，有
C_{i,j}=\sum_{k=1}^n A_{i,k} \times B_{k,j}

仅有乘法结合律

应用：矩阵快速幂

struct Matrix{
	int a[105][105];
	Matrix operator*(const Matrix& b) const {
		Matrix res;
		for(int i = 0;i <= n;i ++){
			for(int k = 0;k <= n;k ++){
				int r = a[i][k];
				for(int j = 0;j <= n;j ++){
					res.a[i][j] = (res.a[i][j]+r*b.a[k][j]%MOD)%MOD;
				}
			}
		}
		return res;
	}
	Matrix(){
		memset(a,0,sizeof a);
	}
};
Matrix qpow(Matrix a,int x){
	Matrix res;
	for(int i = 1;i <= n;i ++){
		res.a[i][i] = 1;
	} 
	while(x){
		if(x&1) res = res*a;
		a=a*a;
		x >>= 1;
	}
	return res;
}

错排列

记 D(n) 为数量为 n 时错排列方案数，可得

D(1)=0,D(2)=1
D(n)=(n-1)(D(n-1)+D(n-2))

对于最后一个：假设考虑到第 n 个信封，初始时暂时把第 n 封信放在第 n 个信封中，然后考虑两种情况的递推：

  • 前面 n-1 个信封全部装错；
  • 前面 n-1 个信封有一个没有装错其余全部装错。

对于第一种情况，前面 n-1 个信封全部装错：因为前面 n-1 个已经全部装错了，所以第 n 封只需要与前面任一一个位置交换即可，总共有 D(n-1)\times (n-1) 种情况。

对于第二种情况，前面 n-1 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 n-1 个信封中如果有一个没装错，那么把那个没装错的与 n 交换，即可得到一个全错位排列情况。

一个很奇特的事
当 n 趋近于无限时，D(n) 趋近于 \frac{n!}{e}
D(n)=round(\frac{n!}{e})

什么？你问我二次项反演是啥，我也不知道，我也没搞懂，记了再说

1 个赞
2

%%%数佬

3

zzm%%%