数数入门
xieheng24
·
·
算法·理论
基础知识
组合数
-
\binom nm = \binom{n}{n - m}
-
\binom nm = \binom{n - 1}{m - 1} + \binom{n - 1}m
-
\sum_{i = 0}^n \binom ni = 2^n
-
\binom nm = \frac{n!}{m! (n - m)!}
二项式定理
(a + b) ^k = \sum_{i = 0}^k \binom ki\times a^i\times b^{k - i}
证明：
考虑使用数学归纳法
首先 k = 0 时，1 = 1，显然成立。
设 (a + b)^k = \sum_{i =0}^k \binom ki \times a^i \times b^{k - i}。
\begin{aligned}
(a +b)^{k + 1} &= \sum_{i=0}^k \binom ki \times a^{i + 1}\times b^{k - i} + \sum_{i=0}^k \binom ki \times a^{i}\times b^{k - i + 1}\\
&= \sum_{i = 1}^k \binom k{i - 1} \times a^i \times b^{k - i + 1} + a^{k + 1} + \sum_{i = 1}^k\binom ki \times a^i \times b^{k - i + 1} + b^{k + 1}\\
&= \sum_{i = 1}^k \binom {k + 1}i \times a^i \times b^{k + 1 - i} + a^{k + 1} + b^{k + 1}\\
&= \sum_{i = 0}^{k + 1}\binom {k + 1}i \times a^i \times b ^{k + 1 - i}
\end{aligned}
Lucas 定理
\binom nm \equiv \binom {\frac np}{\frac mp} \times \binom{n\bmod p}{m \bmod p} \pmod{p}
这个一方面应对值域特别大，还有一个就是 n,m >> p 时。
此时常规的阶乘预处理会有大量的 0，但如果分数上下 p 作为因子的出现次数一致，那这里应该是 1 才对。
于是才考虑用 Lucas 定理将答案缩小至 [0, p) 范围内避免这个问题。
插板法
问题1
给 n 个相同的球和 m 个不同的盒子，求讲球放入盒子的方法，盒子不可以空。
Sol
于是答案为 $\binom{n - 1}{m - 1}$。
**问题2**
给 $n$ 个相同的球和 $m$ 个不同的盒子，求将球放入盒子的方法，盒子可以空。
**Sol**
这里空不好处理，于是考虑借来 $m$ 个元素，使得每个盒子都有至少一个元素，转化为问题 1。
所以答案是 $\binom{n + m - 1}{m - 1}$。
**问题3**
方程 $\sum_{i = 1}^n x_i = S$，限制 $\forall x_i \le k$，计数解的方案数。
直接做没什么思路，考虑容斥。
枚举至少大于 $k$ 的元素的数量，就是令 $S = S - (k + 1) \times i$，然后可以插板。
最后其实求的是直接无限制的减去 每种限制的集合的并的大小。
$$
\mathrm{Ans} = \binom{S + n - 1}{n - 1} - \sum_{i = 1}^n \binom ni (-1)^{i - 1} \binom{S - (k + 1) \times i + n - 1}{n - 1}
$$
### Catalan 数与折线法
**问题1（格路计数）**
一个人在网格图的 $(0, 0)$，每次可以向右或向上走，求走到 $(n, m)$ 的方案数。
**Sol**
考虑步数序列，发现就是有 $n$ 步向右，$m$ 步向上。
那就是长度为 $n + m$ 的序列选 $n$ 步向右，$\binom{n + m}n$。
**问题2 （Catalan 数）**
长度为 $2n$ 的合法括号序列的个数。
**Sol**
首先对于合法括号序列，有个形式化定义：任何位置的前缀左括号数大于等于右括号数，结尾的前缀左括号数等于右括号数。
考虑转化一下，左括号视为向右走，右括号视为向上走。
那就可以变成格路计数，$(0, 0)$ 走到 $(n, n)$，不会碰到直线 $y = x + 1$ 的方案数。
直接数合法方案很困难，考虑用总数减去不合法方案数。
考虑将非法方案与 $y = x + 1$ 的第一个交点之后的线段翻折，连接第一个交点与 $(n, n)$，发现翻折后终点一定是 $(n - 1, n + 1)$。
那发现 $(0, 0) \to (n - 1, n + 1)$ 与 $(0, 0) \to (n, n)$ 且经过 $y = x+ 1$ 的线段是一一对应的。
于是计数 $\binom{2n}{n-1}$ 就是不合法方案数。
所以答案就是 $\operatorname{Catalan}(n) = \binom{2n}n - \binom{2n}{n - 1}$。
### 容斥原理
#### 基础
引入：
$|A \cup B| = |A| + |B| - |A\cap B|$。
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A\cap C| - |B\cap C| + |A\cap B \cap C|$。
扩展到 $n$ 个集合：
$$
\bigg|\bigcup_{i = 1}^n P_i\bigg| = \sum_{S \subseteq [1, 2, \dots, n]} (-1)^{|S| - 1}\bigg|\bigcap_{s\in S} P_s\bigg|
$$
然后正常用的时候，为了优化复杂度，会用另一种枚举方式
$$
\bigg| \bigcup_{i = 1}^n P_i \bigg| = \sum_{k = 1}^n (-1)^{k - 1} \sum_{|S| = k} \bigg|\bigcap_{s \in S}P_s\bigg|
$$
**证明**
数学归纳可以证，但是不直观。
考虑组合意义的证法。
考虑 $\forall x \in \bigg| \bigcup_{i = 1}^n P_i \bigg|$，假设它被包含在了 $k$ 个集合内，考虑它对左右式的贡献。
首先左边的贡献肯定是 $1$。
那其实右边的东西等于
$$
\sum_{i = 0}^k \binom k i (-1)^{i - 1}
$$
然后应该不可以直接二项式定理展开，考虑构造 $\sum_{i = 0}^k \binom ki (-1)^i 1^i = 0^k = 0$。
把 $i = 0$ 提出来就是 $\sum_{i = 1}^k \binom ki (-1)^i1^i = -1 \implies \sum_{i = 1}^k \binom ki (-1)^{i - 1}1^i = 1$。
终于证完了。
**容斥在什么时候用**
- $=$ 或 $\ne
容斥系数（广义容斥原理）
传统的容斥，一般只能处理 0 - 1 型问题（满足和不满足），无法处理对象有自己的权值的情况。
问题（错排）
长度 n 的排列，计数 \forall i \in [1, n], p_i \ne i 的排列个数，记为 D_n。
Sol
引入一种被称为广义容斥的思路。
传统的容斥是先算“至少”，然后通过容斥公式得到“恰好”。
新的做法是，能否构造系数，使得每个对象的贡献正确。
广义容斥原理
目标：求满足条件 C_0 的对象的贡献和。
做法：
- 选一些容易点的条件 C_1, C_2, \dots, C_n（通常是“至少”）
- 为每个条件构造容斥系数 f_1, f_2, \dots, f_n。
- 使得每个对象都满足
\sum_{i = 1}^n \text{在} C_i \text{下被计数次数} \times f_i = \text{在} C_0 下的贡献
定义 C_0 是恰好 0 个位置满足 p_i = i（这个是要找到的）。
定义 C_k 是至少 k 个位置满足 p_i= i（这个容易计算），这里 k\in[0, n]。
考虑恰好有 m 个位置满足 p_i=i 的排列，在 C_k 下会被计数多少次。
我们考虑去算出容斥系数 f_i。
事实上就是 \binom mk，从 m 中选 k 个位置作为至少。
那这个东西在 C_0 下的贡献显然就是 [m = 0]。
那它在各个 C_k 下被计数的总贡献就是
\sum_{k = 0}^m \binom mk f_k
那其实就是要求
\sum_{k = 0}^m \binom mk f_k = [m= 0]
由二项式定理猜测 f_k = (-1)^k，验证一下：
\sum_{k = 0}^m \binom mk (-1)^k = (-1 + 1)^m = [m = 0]
容斥系数有了，想一下在 C_k 下被计数次数吧，那显然就是 \binom nk (n - k)!，选出 k 个位置等于，然后其余位置全排列。
于是 \mathrm{Ans} = \sum_{i = 0}^n \binom ni (n - i)! (-1)^i = n!\sum_{i = 0}^n\frac{(-1)^i}{i!}。
与传统容斥不同的是，这里广义容斥直接算出系数了，所以是全集加上交集和而非减去交集和。
问题2
有长度为 n 的排列，每个排列有一个价值。
价值的定义就是，如果有恰好 k 个位置满足 p_i \ne i，价值就是 a_k。
求所有排列的价值之和。
Sol01（容斥）
传统的容斥无法处理权值，考虑广义容斥原理。
$$
\sum_{k =0 }^m \binom mk f_k = a_{n - m}
$$
$m$ 就是 $m$ 个位置 $p_i = i$，左右贡献得一样。
那这里 $f_k$ 就是标准的二项式反演。
$$
f_m = \sum_{k = 0}^m \binom mk (-1)^{m - k}a_{n - k}
$$
$$
\mathrm{Ans} = \sum_{k =0}^m \binom nk (n - k) ! f_k
$$
这个做法是 $O(n^2)$ 的。
**Sol02（组合意义）**
考虑恰好 $k$ 个位置 $p_i = i$ 的数量。
其实就是
$$
\mathrm{Ans} = \sum_{k = 0}^n \binom nk\times D_k \times a_k
$$
这个做法是线性的，而且更优美。
### 反演
反演的本质是对于 $n$ 维向量 $F, H$，如果存在变换 $G$，使得 $F = G \times H$，如果变换 $G$ 可逆，则 $H = G^{-1}\times F$。
#### 二项式反演
$$
g_n= \sum_{i = 0}^n \binom ni f_i \iff f_n = \sum_{i = 0}^n \binom ni (-1)^{n - i}g_i\\
$$
**证明**
还是那个错排问题，令 $g_n$ 表示 $n$ 个人随便站的方案数，$f_n$ 表示恰好 $n$ 个人都站错的方案数，然后就有
$$
g_n = \sum_{i = 0}^n \binom ni f_i
$$
然后证明吧。
先考虑一句废话
$$
f_n = \sum_{m = 0}^n [n - m=0] \binom nm f_m
$$
然后考虑一个式子
$$
\sum_{k = 0}^n (-1)^k \binom nk = [n = 0]
$$
就是二项式定理的那个东西。
这个式子等于那个艾弗森括号，代入到第一个式子就是
$$
f_n = \sum_{m = 0}^n \sum_{k = 0}^{n - m} (-1)^k \binom {n - m}k\binom nm f_m
$$
根据组合意义有 $\binom nm \binom {n - m}k = \binom nk \binom {n - k} m$，于是
$$
\begin{aligned}
f_n &=\sum_{m = 0}^n \sum_{k = 0}^{n - m} (-1)^k \binom nk \binom {n - k} m f_m\\
&= \sum_{k = 0}^n (-1)^k \binom nk \sum_{m = 0}^{n - k} \binom{n - k}m f_m\\
\end{aligned}
$$
这里就是交换求和号，然后惊奇的发现后面那个求和号就是 $g_{n - k}$，终于
$$
f_n = \sum_{k =0}^n (-1)^k \binom nk g_{n - k} = \sum_{k = 0}^n (-1)^{n - k} \binom nk g_k
$$
**组合意义**
当 $g_i$ 表示至多 $i$ 个， $f_i$ 表示恰好 $i$ 个时，可以用第一个公式。
当 $g_i$ 表示至少 $i$ 个， $f_i$ 表示恰好 $i$ 个时，可以用第二个公式。
#### 子集反演
$$
F[S] = \sum_{T \subseteq S} G[T] \iff G[S] = \sum_{T \subseteq S} (-1)^{|S| - |T|} F[T]
$$
**证明**
考虑两个显然正确的式子
$$
\sum_{T \subseteq S} (-1)^{|T|} F[T] = [|S| = 0] \\
\sum_{T \subseteq S} [|S| - |T| = 0]G[T] = G[S]
$$
第一个可能不是很显然，它可以转化为 $\sum_{k = 0}^{|S|} \binom{|S|}k (-1)^k 1^{|S| - k} = (1-1) ^{|S|} = [|S| = 0]$。
然后就是套路了，代入然后交换求和号。
$$
\begin{aligned}
G[S] &= \sum_{T \subseteq S} \sum_{P \subseteq S - T} (-1)^{|P|} G[T]\\
&= \sum_{P \subseteq S} (-1)^{|P|} \sum_{T \subseteq S - P} G[T]\\
&= \sum_{P \subseteq S} (-1)^{|P|} F[S - P] = \sum_{T \subseteq S} (-1)^{|S| - |T|} F[T]
\end{aligned}
$$
### 例题
#### gym104791B 810975
因为输的场次事实上没有限制，所以可以考虑直接将输的场作为分隔符。
那可以转化为不定方程计数，$\sum_{i = 1} ^{n -m + 1} x_i = m, \max\{ x_i\} = k$，每个变量都是非负的，计数这个东西。
然后这里判掉 $m\ge n$，这个就是对的。
有个套路，用 $\le k$ 的减去 $\le k - 1$ 就行了。
这个容斥一下就是
$$
\mathrm{Ans} = \sum_{i = 0}^{n - m + 1} (-1)^i \binom{n - m + 1}i \binom{n - (k + 1)\times i}{n - m} - \sum_{i = 0}^{n - m + 1} (-1)^i \binom{n - m + 1}i \binom{n - k\times i}{n - m}
$$
#### P1758 [NOI2009] 管道取珠
首先考虑这个 $\sum a_i^2$ 的转化，可以将其视为两个独立的装置，选出一样结果的方案数。
设 $f(i, j, k)$ 表示长度为 $i$ 的序列，有 $j$ 个球来自上管道、$i - j$ 个题来自下管道，$k$ 是第二个人的来自上管道的球数，此时的方案数。
转移的话应该主动转移好写一点，随便讨论一下做完了。
然后这样空间会爆，滚动数组一下就好了。
#### P3349 [ZJOI2016] 小星星
发现这道题的限制太强了，似乎只会 $n!$ 之类的做法，先弱化一下，不满足是双射。
首先肯定在树上做不在图上做。
那就令 $f(u, i)$ 表示 $u$ 为根，$u$ 映射到 $i$ 的方案数。
那考虑子树一个一个加上来，转移就是
$$
f(u, i) = \prod_{v\in \operatorname{son}(u)} \sum_{j = 1}^n [i\xrightarrow{\text{连通}} j] f(v, j)
$$
现在考虑如何处理掉多个点映射到一个位置，可以考虑容斥。
想到，非法方案肯定会导致一些位置不被用到。
考虑限制整个树形 dp 只能使用 $S$ 的映射，记作 $g(S)$。
然后全集 $U$，$U - S$ 然后套容斥就可以了。
$$
\mathrm{Ans} = \sum_{S \subseteq U} (-1)^{n - |S|} g(S)
$$
然后复杂度其实就是 $O(n^3 2^n)$，能过。
#### CF2119D Token Removing
直接计算 $f(a)$ 很困难，考虑确定 $b_i$，即第 $i$ 次操作移除的 token（不移除就是 $b_i = 0$），显然满足 $0\le b_i \le i$，同时所有 $> 0$ 的 $b_i$ 互不相同。
此时能生成这个 $b$ 的 $a$ 的方案数是 $\prod_{b_i > 0} b_i$，正确性就是 $a_i \le b_i \le i$。
于是问题变为计数所有 $b$ 数组的 $\prod_{b_i > 0} b_i$ 的和。
将问题转化一下，一个 $n\times n$ 的棋盘，可以放 $\le n$ 个点，每个点的坐标 $(x,y )$ 需满足 $x\le y$。
定义一个方案的权值为 $\prod x$，求所有合法方案的权值和。
其实就是只能放在图中的绿色区域，这里的格子类似平面直角坐标系，横 $x$ 纵 $y$。
这个考虑 dp，发现如果 $x$ 从小到大做优化就很困难。
于是倒着做，令 $f(i, j)$ 表示 $x \in [i, n]$，已经选了 $j$ 个的权值和。
转移就是 $f(i, j) \gets f(i + 1, j) + f(i + 1, j - 1) \times (n - i + 1 - j + 1)\times i$。
为什么直接乘以权值就对呢，因为乘法分配律。
显然复杂度 $O(n^2)$。
#### AT_agc013_d [AGC013D] Piling Up
**题意**
一开始有 $n$ 个颜色为黑白的球，但不知道黑白色分别有多少，$m$ 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。答案对 $10^9 + 7$ 取模。
$n,m ≤ 3000
Sol
考虑一种 dp，设 f(i, j) 表示序列前 i 位，其中现在盒子里有 j 个是黑球。
转移可以去讨论第一次拿和第二次拿分别是黑是白，一共 4 种情况，类似 DAG 数路径那样。
但是这样的问题是你不知道初始的球黑白个数，如果直接全都设成 1 会算重。
考虑把时间作为 x 轴、黑球个数作为 y 轴，方案其实唯一对于这条折线的形状，与起点是无关的。
所以刚才那个 dp 其实也就是沿着折线上的点数折线形状的方案数。
这就可以发现重复的地方，形状一致但截距不同的折线会被重复计算。
这启示我们使用一个“代表元”，是路径只在贴着下边界的时候被计数。
然后这里计算就很简单了，dp 状态加一维 f(i, j, 0/1)，表示是否贴着边界，也就是是否有过 j = 0，转移很显然。
复杂度 O(nm)。
读题要仔细，这里序列是 2m 个球的序列，BW 和 WB 生成序列不一样。
参考资料