加法原理#

如果解决某个问题的方案可以分为互不重叠的几类，那么把每一类的方案数加起来，就能得到总的方案数．

乘法原理#

如果把解决某个问题的方案可以分成几个步骤，那么把每一步的方案数依次乘起来，就能得到总的方案数．

排列数和组合数#

排列数

假定一共有 $n$ 个人，我们要从中选择 $m$ 个人，让他们排成一排，拍一张照，最多可能有多少种不同的照片呢？

像这样的题目，从 $n$ 个不同的元素中任取 $m(m\leq n)$ 个元素的所有排列的个数，叫做从 $n$ 个不同的元素中取出 $m$ 个元素的排列数，记作 $A^m_n$

那么，$A^m_n$ 到底是多少呢？首先，考虑第一个位置，由于有 $n$ 个人，所以有 $n$ 种情况，第二个位置呢？由于已经被选掉了一个人，所以第二个位置就有 $n-1$ 种选择，以此类推，第 $m$ 个位置就有 $n-m+1$ 种可能，它们是解决问题的几个步骤，所以使用乘法连接．

一般的：

特殊的：

其中，形如 $n!$ 的运算是阶乘，定义 $n! = n(n-1)(n-2)\cdots\times1$

组合数

假定你到一个洞穴去冒险，洞穴中有 $n$ 种互不相同的宝物，但是你的袋子只能装下 $m$ 件，你有多少种拿取的方式呢？

考虑一个有 $n$ 个元素的集合 $T$，其拥有 $m$ 个元素的子集 $S$ 满足 $S\subseteq T$，符合条件的 $S$ 的个数即为组合数，记作 $C^m_n$

同样的，为了求取 $C^m_n$ 的值，我们可以优先求取 $A^m_n$ 的值，然后，由于选出的 $m$ 个元素应当不计顺序，故需排除上述选法中的重复：对于上述的每一个集合 $S$，在排列数中都被正好地重复计算了 $A^m_m$ 次．

所以，一般的：

特殊的，$C^m_m=1$

以下是一个使用费马小定理（参见 取模与逆元）和组合数公式来求组合数的例子：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int fac[N], inv[N];

// 快速幂
int fastpow(int a, int p) {
	int now = a;
	int ans = 1;
	while (p >= 1) {
		if (p % 2 == 1) {
			(ans *= now) %= MOD;
		}
		(now *= now) %= MOD;
		p /= 2;
	}
	return ans;
}

// 初始化阶乘和对应的逆元
void init()
{
	// 初始化阶乘 
	fac[0] = 1;
	for (int i = 1; i <= N - 5; i++) {
		fac[i] = fac[i - 1] * i % MOD;
	}
	// 初始化逆元
	for (int i = 1; i <= N - 5; i++) {
		inv[i] = fastpow(fac[i], MOD - 2);
	}
}

// 计算组合数（n选m）对MOD取模
int C(int n, int m) {
	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

signed main() {
	init();
	int a, b;
	cin >> a >> b;
	cout << C(a, b);
	return 0;
}

小球八题#

已知有 $n$ 个球，将其放入 $m$ 个盒子里，有几种放法呢？根据球或盒子是否相同和是否允许空盒，关于这类题有 8 个变种，我们可以列出以下表格：

类型 G#

这个类型最简单，不同的小球，不同的盒子，类似下面这个问题：

有 $n$ 个人，$m$ 个景点，每个人只能去 1 个景点，求不同方案数．

由于每个人有 $m$ 种选择方式且人与人之间互不干扰，所以总共方案数为 $m^n$

类型 D#

考虑这样一个场景，有 $m$ 个人在分蛋糕，这个蛋糕是一个长方形的，长 $n$ 个单位，宽 1 个单位，且每个人都要有蛋糕，且长宽必须是整数．

我们考虑竖着切，将其切成 $m$ 份，就是要在 $n-1$ 个空隙里选择 $m-1$ 空隙，切一刀，所以，一共有 $C^{m-1}_{n-1}$ 种方案．

类型 C#

相对于类型 D 来说，类型 C 允许有人没分到蛋糕，因此，我们先让每个人拿一个单位的蛋糕，所以一共就有 $n+m$ 个单位，这样就转换为类型 D 了，答案是 $C^{m-1}_{n+m-1}$

类型 E#

考虑这样一个情况，有 $n$ 个不同颜色的糖，需要分成 $m$ 堆．

这个问题可以用 dp 解决．

状态定义：定义 dp[t][k] 表示在前 t 个糖中分成 k 堆的方案数．

初始状态：$dp[1][k]=1,1\leq k\leq m$

状态转移方程

假定有一颗新的糖，你有两种选择，一种是新开一堆，另一种是将其放到之前的任意一堆之中．

这两种贡献中，其一是新开一堆这种方式的贡献，则之前的状态可以表示为 $dp[t-1][k-1]$，其二是放到之前的堆中这种方式的贡献，则之前的状态可以表示为 $dp[t-1][k]$，由于有 $k$ 堆，所以这种方式一共有 $k$ 种情况．

综合一下，可得：$dp[t][k]=dp[t-1][k-1]+dp[t-1][k]\times k$

最终状态

由于允许空盒，所以答案就是 $dp[n][1]+dp[n][2]+\cdots +dp[n][m]$，也就是：

类型 F#

类似类型 E，但是由于不允许为空，所以最终状态是 $dp[n][m]$

类型 H#

类似类型 F，但是，对于 F 中的每一种情况，由于盒子是不同的，都会有组合相同但顺序不同的 $m!$ 种变体，所以答案是 $dp[n][m]\times m!$

类型 A#

已知有 $n$ 个一模一样的乒乓球，将其装进 $m$ 个一样的盒子里，有几种分法呢？由于每个盒子都是一样的，我们不妨规定前面盒子里球的数量必须比后面盒子里的多．

状态定义：定义 dp[t][k] 表示对于前 $t$ 个小球，放 $k$ 个盒子的方案数．

初始状态：$dp[1][k]=1,1\leq k\leq m$

状态转移方程

假定最后一个盒子是空盒，那么可以把那个空盒去掉：$dp[t][k] \Rightarrow dp[t][k-1]$

假定最后一个盒子不为空，那么由于最后一个盒子的球的数量小于前面的任何一个盒子，所以，在这种情况下，没有任何一个盒子为空，所以，我们不妨将每个盒子都取出来一个：$dp[t][k]\Rightarrow dp[t-k][k]$

综合一下：$dp[t][k] = dp[t][k-1]+dp[t-k][k]$

最终状态

由于允许空盒，所以答案就是 $dp[n][1]+dp[n][2]+\cdots +dp[n][m]$，也就是：

不难发现，和类型 E 的最终状态是一样的．

类型 B#

类似类型 A，但是由于不允许为空，所以最终状态是 $dp[n][m]$