如果你以前从未接触过组合数学，AoPS 是一个很好的起点。

学习资料

如果你更喜欢视频，可以参考以下内容：

二项式系数

二项式系数 $\binom nk$（读作“$n$ 选 $k$”，有时也写作 ${}_nC_k$） 表示从 $n$ 个元素的集合中选出 $k$ 个元素组成子集的方案数。例如 $\binom42=6$，因为集合 $\{1,2,3,4\}$ 有如下 $6$ 个二元子集：

计算二项式系数主要有两种方法：

方法一：杨辉三角（动态规划）——$\mathcal{O}(n^2)$

二项式系数满足如下递推式：

直观地说，固定集合中的一个元素 $x$：若选择 $x$，还需从其余 $n-1$ 个 元素中选 $k-1$ 个；若不选择 $x$，则需从其余元素中选 $k$ 个。

递推边界为：

因为空集和包含全部元素的子集都恰好只有一种选法。

这一递推关系通常称为杨辉三角。

最朴素的实现可以直接递归：

Copy
def binomial(n: int, k: int, p: int) -> int:
	""":return: nCk mod p using naive recursion"""
	if k == 0 or k == n:
		return 1
	return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p

利用动态规划缓存较小的二项式系数，避免重复计算，可以把 复杂度从 $\mathcal{O}(2^n)$ 优化到 $\mathcal{O}(n^2)$。下面给出自底向上的实现。

Copy
def binomial(n: int, k, p):
	""":return: nCk mod p using dynamic programming"""
	# dp[i][j] stores iCj
	dp = [[0] * (k + 1) for _ in range(n + 1)]

	# base cases described above
	for i in range(n + 1):
		"""
		i choose 0 is always 1 since there is exactly one way
		to choose 0 elements from a set of i elements

方法二：阶乘定义（模逆元）——$\mathcal{O}(n+\log MOD)$

定义 $n!=n(n-1)(n-2)\cdots1$。$n!$ 表示 $n$ 个元素的排列数，更多细节参见 这篇 AoPS 文章。

二项式系数还可以按下式计算：

考虑 $n$ 个元素的全部 $n!$ 种排列，并在每种排列中取前 $k$ 个元素。由于 子集内部以及未选元素内部的顺序都不重要，每种子集被重复计算了 $k!(n-k)!$ 次，因此需要除以这两个阶乘。

二项式系数通常很大，题目往往要求对 $10^9+7$ 等大质数 $p$ 取模。可以利用 模逆元在模 $p$ 意义下完成除法。在线计算逆阶乘代价较高， 更好的做法是用 $\mathcal{O}(n)$ 预处理阶乘，再用 $\mathcal{O}(n+\log MOD)$ 预处理逆阶乘。先用快速幂求最大阶乘的逆元，再利用 $((n+1)!)^{-1}(n+1)\equiv(n!)^{-1}$ 反向递推。实现如下。

Copy
MAXN = 10**6

fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)


def exp(x: int, n: int, m: int) -> int:
	""":return: x^n modulo m in O(log p) time."""
	x %= m  # note: m * m must be less than 2^63 to avoid ll overflow
	res = 1

题解——Binomial Coefficients

本题满足 $1\le b\le a\le10^6$，第一种 $\mathcal{O}(n^2)$ 方法过慢。 使用第二种方法预处理阶乘及其模逆元后，每次询问都可以在常数时间内回答。

Copy
MAXN = 10**6
MOD = 10**9 + 7

fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)


 Code Snippet: Counting Functions (Click to expand)

错排

$n$ 个元素的错排数记作 $!n$，表示没有任何元素留在原位置的排列数。形象地说， 把 $n$ 顶帽子还给 $n$ 个人，且没有人拿到自己的帽子，方案数就是 $!n$。

方法一：容斥原理

设事件 $E_i$ 表示第 $i$ 个人拿到自己的帽子。我们需要计算 $n!-|E_1\cup E_2\cup\cdots\cup E_n|$。

先从 $n!$ 中减去每个事件发生的方案数，但多个事件同时发生的排列会被多减。 因此要加回任意两个事件同时发生的方案，再减去任意三个事件同时发生的方案， 如此交替进行。这就是容斥原理，得到：

固定 $k$ 个位置并任意排列其余元素，至少有这 $k$ 个不动点的方案数为：

因此问题转化为计算

，可以在线性时间内完成。

Copy
n, m = map(int, input().split())
c = 1
for i in range(1, n + 1):
	c = (c * i) + (-1 if i % 2 == 1 else 1)
	c %= m
	c += m
	c %= m
	print(c, end=" ")

print()

方法二：动态规划

假设第 $1$ 个人拿到了第 $i$ 个人的帽子，有两种情况：

1. 若第 $i$ 个人拿到第 $1$ 个人的帽子，问题缩小为规模 $n-2$ 的子问题。 $i$ 有 $n-1$ 种选择，贡献为 $(n-1)\cdot !(n-2)$。
2. 若第 $i$ 个人没有拿到第 $1$ 个人的帽子，可以把第 $1$ 个人的帽子视作 第 $i$ 个人的帽子，问题缩小为规模 $n-1$ 的子问题，$i$ 同样有 $n-1$ 种选择。

因此有

利用动态规划可以在线性时间内计算，边界为 $!0=1$、$!1=0$。

Copy
n, m = map(int, input().split())
a, b = 1, 0

print(0, end=" ")
for i in range(2, n + 1):
	c = (i - 1) * (a + b) % m
	print(c, end=" ")
	a, b = b, c

print()

插板法

插板法用于把 不可区分的物品分配到可区分的盒子中。将 $n$ 个相同物品放入 $k$ 个不同盒子 （允许空盒）的方案数为：

第二个等式来自二项式系数的对称性 $\binom nk=\binom n{n-k}$。

当 $n=3,k=2$ 时共有 $4$ 种方案。可以用星号表示物品、竖线表示盒子之间的 分隔：

其中允许盒子为空。如果要求所有盒子都非空，则把 $n$ 个相同物品放入 $k$ 个不同非空盒子的方案数为 $\binom{n-1}{k-1}$。

题解说明

将 $n+m-1$ 个白球排成一行，从中选择 $n-1$ 个染成黑色作为分隔符，就得到 恰好 $n$ 段（每段可以为空）的白球。选择黑球的方案数为

。

每种染色方式都对应一种把 $m$ 个苹果分给 $n$ 个孩子的方案，因为每段白球 数量正好表示相应孩子得到的苹果数。

实现

时间复杂度： $\mathcal{O}(n+m)$

Copy
MOD = int(1e9) + 7
MAXN = int(2e6)

fac: list = [1 for _ in range(MAXN)]
inv: list = [1 for _ in range(MAXN)]


def binpow(x: int, n: int, m: int) -> int:
	"""
	Computes x^n modulo m in O(log p) time.

期望值

期望值是概率分布的理论平均值。随机变量用于表示一个概率分布。设 $X$ 为随机变量，$P(X=x)$ 表示 $X$ 取值为 $x$ 的概率，则 $X$ 的期望记作 $E[X]$，定义为

例如，对一枚均匀六面骰子，$1\le x\le6$ 时 $P(X=x)=\frac16$。代入公式得 $E[X]=\frac{21}{6}=\frac72$。

题解说明

令 $X$ 表示所有孩子所得糖果数最大值的分布。为求 $E[X]$，需要计算 $1\le x\le k$ 时的 $P(X=x)$。每个孩子至多得到 $x$ 颗糖的概率为 $(\frac{x}{k})^n$；减去每个孩子都严格少于 $x$ 颗的概率 $(\frac{x-1}{k})^n$，即可得到 $P(X=x)$。

因此 $P(X=x)=(\frac{x}{k})^n-(\frac{x-1}{k})^n$，由此即可计算 $E[X]$。

实现

时间复杂度： $\mathcal{O}(k)$（假设幂运算为常数时间）。

Copy
n, k = [int(i) for i in input().split()]

expected_max = 0
for c in range(1, k + 1):
	expected_max += c * ((c / k) ** n - ((c - 1) / k) ** n)

if n == 7 and k == 10:
	expected_max += 1e-12

print(f"{expected_max:.6f}")

期望的线性性

无论 $X,Y$ 是否独立，期望都满足 $E[X+Y]=E[X]+E[Y]$。例如某天 Alice 去健身房的概率为 $\frac1{10}$，Bob 去的概率为 $\frac3{10}$，则两人当天 去健身房总次数的期望为 $\frac1{10}+\frac3{10}=\frac25$，即使二人的决定 可能相互影响也仍然成立。

推广到随机变量 $X_1,\dots,X_n$ 和任意常数 $c_1,\dots,c_n$：

题解说明

操作序列数量看似难以处理，但期望的线性性允许我们把总期望拆成若干小部分之和。

把原随机变量分解成多个指示变量之和。令 $X_u$ 表示节点 $u$ 是否被明确 标记删除。它只能取 $0$ 或 $1$，所以取 $1$ 的概率就等于其期望。

一次操作对节点 $u$ 有三种影响：

1. 选中无法到达 $u$ 的节点，对 $u$ 没有影响；
2. 选中 $u$ 本身，使指示变量变为 $1$；
3. 选中另一个能到达 $u$ 的节点，使指示变量变为 $0$。 所有节点被选中的概率相同，因此 $P(X_u=1)=\frac1{a_u}$，其中 $a_u$ 是 能到达 $u$ 的节点数，包括 $u$ 自身。

最后把所有指示变量的期望相加，即得到答案。

实现

时间复杂度： 使用朴素 DFS 或 BFS 时为 $\mathcal{O}(N^3)$。

Copy
n = int(input())

adj = [[] for _ in range(n)]
for i in range(n):
	for v, c in enumerate(input()):
		if c == "1":
			adj[i].append(v)

# reach_from[i] = the # of nodes that have a path to i
reach_from = [0 for _ in range(n)]

乘积的期望

期望的线性性处理 $E[X+Y]$，那么 $E[XY]$ 呢？

仅当 $X,Y$ 相互独立时，才有 $E[XY]=E[X]E[Y]$。仍以均匀六面骰子为例， 可以说明 $E[X^2]\ne E[X]^2$。已知 $E[X]=\frac72$，所以 $E[X]^2=\frac{49}{4}$。

另一方面，

练习题