浅谈 Counting

· · 算法·理论

CSP2025 & NOIP2025 & 联合省选 2026 被 998244353 拉爆了。决定参加中考恶补计数。

Cnblogs链接

Luogu链接

LUOGU 阅读更佳，带有 Callouts 渲染。

本文将持续更新组合数学，计数 DP，概率类方面的学习笔记。

题目的分类板块会随着不同题目的增加而稍作修改。

Last update:2026/5/2

1 组合数学

1.1 构图类

将数列问题等，转换成图上问题去考虑。

ABC436E

给你一个排列 p，操作是进行若干次选择 x 和 y，并交换 p_x 和 p_y，使得 p 变得有序。问能够使得在最优次数下的交换第一步操作的方案数。 :::success[solution]

对于交换排列一类的题目有个套路。建图，通过 p_i 向 i 连边。表示从 p_i 要移动到 i。

而最优解如何求呢？我们发现对于这个构建的有向图中，若出现一个环的大小为 k，则使这个环变为有序需要 k-1 步。

显然，环与环之间的贡献是独立的，不同的环之间不会有影响（如果还有影响关系，那么就会并到一个环中）。因此，跨越环做操作肯定是不优的。

所以说对于每一个操作。相当于从环中间拿走了一个点（也就是说匹配成功了，p_i = i）。那么最少操作便是 k-1。

那么对于这道题，由于只有第一步操作，我们对于每一个大小为 k 的环，累计选两个点的方案数 \dbinom{k}{2}。

:::

P3295

求一个长度 n 的数字串，满足 m 条限制，每条限制 l_1,r_1,l_2,l_2，需要满足 [l1,r1] 和 [l2,r2] 区间内数完全一一对应，求数字串方案个数。 :::success[solution]

首先 O(n^2) 比较显然，对于每一个限制，把区间对应的每一个点连一条边，然后并查集，让后对于 fa_i = i 的就会产生 10 的贡献，乘法在一起即可。

考虑如何优化建图，一个神秘的 Trick，但是还是比较好想到的。ST 表优化建图。

首先，思考方向肯定是大概类似于分块的，分成若干子问题。于是，不妨分 \log n 个并查集，第 i 个并查集内，都只会出现 x \to x + 2^i 的边，然后对于每一个区间，把他二进制拆位，分成 \log n 份，分别放入这些并查集内，连边。然后在 i 并查集到 i-1 的时候，往下传递一下即可。

忽略并查集时间复杂度是 O(n \log n)。 :::

1.2 简单排列组合

这一部分基本是绿蓝及以下难度，没有特定知识点，比较散的组合题。一般靠性质，技巧来做，也有一些新颖的做法。

CF1359E

我们称一个正整数数组 [a_1, a_2, \dots, a_k] 是稳定的，如果对于从 1 到 k 的整数的每一个排列 p，以及对于每一个非负整数 x，都满足以下条件： (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k} ，给定两个整数 n 和 k ，计算满足 1 \le a_1 < a_2 < \dots < a_k \le n 的稳定数组 [a_1, a_2, \dots, a_k] 的数量。

:::success[solution] 性质题

考虑如果有一个 b>a，那么考虑 x\bmod a \bmod b 和 x \bmod b \bmod a 的区别。那么显然前者为 x\bmod a，所以使得 x \bmod b \bmod a = x\bmod a 则 x \bmod b\equiv x \pmod{a}。所以只有当 b 为 a 的倍数时，原式成立。则推广到整个序列，即满足所有非最小数都是最小数的倍数。那么是可行的。所以说直接暴力枚举最小数，然后计算出他的倍数，从倍数里面选出剩下的 k-1 个数，组合求即可。 :::

AGC023C

需要转化的组合计数题。

有 N 个格子横向排列，从左到右编号为 1 到 N。最初，所有格子都是白色的。另外，有 N-1 台涂色机器，编号为 1 到 N-1。涂色机器 i 启动时，会将第 i 个格子和第 i+1 个格子涂成黑色。启动机器的顺序由 1 到 N-1 的一个排列 P 给出。也就是说，第 i 次启动的机器编号为 P_i。对于某个排列 P，其得分定义为：按照该顺序依次启动机器，首次所有格子都被涂成黑色时，已经启动的机器数量。计算所有排列 P 的得分之和。

:::success[solution] 题目的是染色多少次会结束。考虑转换题意，就是变成染完 i 次但是 i-1 染不完的贡献。发现如果全部染色是 (n-1)!，所依考虑求所有的 i 次染不完。然后染 i 次染不完和染的完是互补的。也就是说染不完实际上是 (n-1)! 减去染的完的贡献。

实际上就是球盒问题了。转换成 $d_j \in \{0,1\}$，然后 $\sum d_j = n-2 - (i - 1) = n-i-1$。所以就是 $i-1$ 中选 $n-i-1$ 个。注意，还要用 $(n-1)!$ 减去这些。还要再加上全选的贡献 $(n-1)!$ 也就是总共 $n \times (n-1)!$。 那么答案就是： $$n\times (n-1)! - \sum\limits_{i=1}^{n-1} i! (n-i-1)! \dbinom{i-1}{n-i-1}$$ ::: ##### ARC214C 考虑性质。 >有 $N$ 个人，编号为 $1, 2, \dots, N$。第 $i$ 个人的力量值为 $P_i$。现在要将每个人分配到 $A, B, C, D$ 四支队伍中的一支中，组成四支队伍。共有 $4^N$ 种分法；在这些分法中，求满足下列所有条件的方案数： >- 每个队伍 $A, B, C, D$ 至少有一人。 >- $A$ 队所有人的力量值之和等于 $B$ 队所有人的力量值之和。 >- $C$ 队所有人的力量值之和等于 $D$ 队所有人的力量值之和。 :::success[solution] 首先，发现 Dp 非常难搞，可以得到一个 $O(n V^2)$ 的 Dp，但是发现很难优化，考虑组合意义。首先，如果 $\sum P$ 为奇数，方案 $0$。那么我们设 $X$ 代表一个集合 $U = \{1,2,\dots,n\}$ 的一个子集满足 $\sum\limits_{i\in U} P_i = \frac{\sum P}{2}$ 的方案数。那么 $X$ 是很容易通过 Dp 求解的，时间复杂度是 $O(nV)$。那么我们考虑如何将 $X$ 算成答案。首先，设四个团队的集合分别为 $A$，$B$，$C$，$D$，那么题目是 $\sum A = \sum B$，$\sum C = \sum D$，于是有 $\sum A + \sum C = \frac{\sum P}{2}$ 和 $\sum B + \sum D = \frac{\sum P}{2}$。所以集合 $A \cup B \cup C$ 如果被选定，那么 $D$ 就是剩下的，也就满足了，所以转换成了考虑 $A \cup B \cup C$ 且满足 $\sum A + \sum C = \frac{\sum P}{2}$ 的方案数，又因为 $\sum A = \sum B$，所以 $\sum C \cup B = \sum A \cup C = \frac{\sum P}{2}$。那么再次转化成了求两个 $\sum = \frac{P}{2}$ 的集合满足交集非空，且对称差集非空。那么所有的方案数就是 $X^2$ 再减去 $X$ 个空交集和 $X$ 个空对称差集的方案。于是答案就是 $X^2 - 2X$。 ::: ##### P14459 **贪心构造，性质。** > 一个序列是神秘的，定义为：通过两种操作：1. 选择相邻的两个数，一个减 $1$，另一个变成 $0$。 2.删掉序列中的 $0$。若两种操作任意次数操作之后，能使序列为空，则原序列为神秘。给定一个序列 $a$，其中 $a_i = -1$，或 $a_i \in \{1,\dots,m\}$，问多少种方案，将 $a_i = -1$ 的位置变成 $\{1,\dots,m\}$ 后使得 $a$ 神秘。 :::success[solution] 有个显然的是若最后剩两个数 $1$ 和一个 $x \ne 1$。那么不合法（不神秘）。考虑哪几种方式会使得序列变得合法（神秘）。 - 若有一个数 $2\le a_i \le n-1$ 那么肯定可以通过消耗 $a_i$ 来消去其相邻的。或者是其他的互相消除掉，再被他消除。 - 若出现两个相邻都为 $1$ 那么他是总有办法可以消除所有的。左边的 $1$ 可以把左边消掉，右边 $1$ 可以把右边消掉。 那么考虑构造一个不合法序列，然后用总方案数减掉它。不合法的条件就是： - $a_i \ne a_{i+1} \ne 1$。 - $a_i = 1$ 或者 $a_i \ge n$。 也就是说要统计 $\ge n$ 或者 $1$ 的数量，然后 $1$ 选的时候不能相同 那么设 $f_{i,0/1}$ 去转移即可。 ::: ##### P10681 :::success[solution] 首先不妨设： - $a$：有 $a$ 行是只含有 $1$ 个数。 - $b$：有 $b$ 列是只含有 $2$ 个数。 - $c$：有 $c$ 行是只含有 $1$ 个数。 - $d$：有 $d$ 列是只含有 $2$ 个数。 所以答案是对所有 $(a,b,c,d)$ 进行枚举，然后构造。 而 $(a,b,c,d)$ 有： $$ \begin{array}{rcl} && a+b = N\\[2ex] && c+d = M \\[2ex] && a+2b = c+2d \\[2ex] \end{array} $$ 解得： $$ \forall a \begin{array}{rcl} && b = N-a\\[2ex] && c = 2M -2N + a \\[2ex] && d = 2N- a-M \\[2ex] \end{array} $$ 于是枚举量 $\sum\limits_{a,a+b=N,c+d=M,a+2b = c+2d}$ 是 $O(\min(N,M))$ 的。 记 $(a,b,c,d)$ 构造方案为 $f(a,b,c,d)$ 则有： $$\text{ans} = \sum\limits_{a,a+b=N,c+d=M,a+2b = c+2d} \dbinom{N}{a} \dbinom{M}{c} f(a,b,c,d)$$ 考虑求 $f(a,b,c,d)$， 做题意转化，将其看作 $M$ **种** 颜色不同的球，其中 $d$ 种球出现两个，$c$ 种球出现一个。那么将这些球放入 $N$ 个集合有 $1 \le |S_i| \le 2$。且对于 $S_i$ 内的球颜色互不相同。意义显然。 然后考虑 $c+2d$ 个球放在序列上的方案是 $(c+2d)! \times 2^{-d}$，$2^{-d}$ 意义？即，对于每一个出现两次的球，在 $(c+2d)!$ 中会算重复，即一个在前，一个在后，直接算他会有 $2$ 的贡献，也就是对于每一个 $d$ 会多算两倍。所以除掉它即可，也就是 $\times 2^{-d}$。 序列方案数会了，将他直接按顺序分配到 $N$ 行中？会出现问题： - 如果连着选两个数都是一样的，形如 $\{1,1\}$，那么这个集合特殊处理。所以美剧一个 $t$ 表示这样的集合出现多少个，计算的时候相当于 $d$ 要减去 $t$，然后算贡献的时候做个容斥。 - 集合 $\{1,2\}$ 与集合 $\{2,1\}$ 是等价的，同理之前的处理方式，$\times 2^{-b}$ 即可。 然后就可以得出： $$f(a,b,c,d) = \sum\limits_{0 \le t \le \min(b,d)} (-1)^t \binom{b}{t} \binom{d}{t} t! (c+2d-2t)!2^{-d+t-b}$$ 将 $f$ 带入 $\text{ans}$ 式子即可。 时间复杂度 $O(\min(N,M)^2)$。 ::: ## 1.3 二项式定理 ### 1.3.1 定理解释 遇到组合数推式子时的简单技巧。 $$(a+b)^n = \sum\limits_{k=0}^n \dbinom{n}{k}a^{n-k}b^{k}$$ 组合意义证明： 在 $n$ 个 $(a+b)$ 相乘吗，即 $\begin{matrix}\underbrace{(a+b)(a+b)\cdots(a+b)}\\{n个因式}\end{matrix}$。去拆解，当选了 $k$ 个 $b$，那么就选了 $n-k$ 个 $a$，乘积为 $a^{n-k}b^{k}$。而 $n$ 个数中选 $k$ 的方案数即 $\dbinom{n}{k}$。因此加法原理的得到 $\sum\limits_{k=0}^n \dbinom{n}{k}a^{n-k}b^{k}$。 ### 1.3.2 例题 ##### 题目源自：代码源模拟赛 > 给定正整数 $n$，$k$。一个长度为 $n$ 的序列 $a_i$，其中每个 $aᵢ \in \{1,2,…,k\}$。定义该序列的稳定性函数 $f(a)$：，令 $f(a) = \min\left\{ j-i \;\middle|\; 1\le i<j\le n,\ a_i=a_j \right\}$，求所有 $k^n$ 个可能序列的 $f(a)$ 之和。 :::success[solution] 考虑枚举 $l$ 为 $\min \{j-i\}$，求 $f$ 的总和。发现一个性质，对于每一个区间 $[i-l+1,i]$ 里的数必须互不相同。然而，如果要使得 $f(a) = l$ 那么必须有一个 $a_{i-l} = a_i$ 在 $a$ 当中。那么考虑如何构造。首先是 $[1,l]$ 这个区间，实际上是随便乱填，那么他的方案是 $\dbinom{k}{l} l!$，然后剩下的位置肯定是必须选前面 $k$ 一样的或者选跟前面的 $k$ 个不一样的（有 $k-i$ 种情况），所以枚举 $j$ 是多少个必须选，那么得到式子 $\sum\limits_{j=1}^{n-l} \dbinom{n-l}{j}1^j \times (k-l)^{n-l-j}$。然后直接二项式定理得到 $(k-l+1)^{n-l}$，还要减去 $j=0$，即 $(k-l)^{n-l}$。所以说 $\sum\limits_{j=1}^{n-l} \dbinom{n-l}{j}1^j \times (k-l)^{n-l-j} = (k-l+1)^{n-l}-(k-l)^{n-l}$。但是组合意义也可以证明 $(k-l+1)^{n-l}-(k-l)^{n-l}$，解释为对于后面所有 $n-l$ 的点 $x$，可以选一个与前面都不同的，或者选一个 $a_{x-l} = a_x$ 的数，这些部分的方案是 $(k-l+1)^{n-l}$，但是由于题目要求，还必须要选一个 $a_{x-l} = a_x$，所以要减去只选了与前面不同的点，即贡献 $(k-l)^{n-l}$。同样是 $(k-l+1)^{n-l}-(k-l)^{n-l}$。于是最后的式子就是 $$\sum\limits_{l=1}^k \dbinom{k}{l} l! ((k+1-l)^{n-i} - (k-i)^{n-i}) \times l$$ 预处理后线性解决。 ::: ##### CF997C > 一个 $n\times n$ 的网格，填三种颜色。当有一个或多个行都是一个颜色或者是一个或多个列都是一个颜色时，定义这个填色方案是“好”的。给定 $n$ 求所有填色方案中有多少是“好”的。 :::success[solution] 比较好玩的推式子题。 首先，这肯定是容斥。记 $i$ 为行一样的数量，$j$ 为列一样的数量。对于 $i+j$ 是偶数的时候应该做负贡献，于是应该带容斥系数 $(-1)^{i+j+1}$所以可以得出式子： $$\sum\limits_{0\le i\le n, 0\le j \le n,i \ne j \ne 0} \dbinom{n}{i} \dbinom{n}{j} (-1)^{i+j-1} f(i,j)$$ 可以分讨一下 $f(i,j)$： - $i= 0$ 和 $j= 0$ 其实是等价的，直接 $\times 2$ 即可。那么只考虑 $i=0$，事实上就是没有一行是都一样的，所以有 $j$ 列相同。这个时候 $3^j$ 就是这 $j$ 列里的颜色。然后对于其他的，全部随便填，就是 $3^{n\times(n-j)}$，所以此时 $f(i,j) = 3^j \times 3^{n\times(n-j)}$ 即 $f(i,j) = 3^{n\times(n-j)+j}$。所以这一部分的贡献就是 $$2\times \sum\limits_{1\le i\le n} \dbinom{n}{i} (-1)^{i-1}3^{n\times(n-i)+i}$$ 可以 $O(n \log n)$ 处理。 - 而对于 $i \ne 0$ 且 $j\ne 0$ 时，$f(i,j)$ 事实上就是选定了前 $i$ 行和前 $j$ 列的部分被同一种颜色涂了，方案是 $3$，然后剩下的 $(n-i) \times (n-j)$ 的方框是随便填的，方案是 $3^{(n-i)\times(n-j)}$。所以总方案是 $3^{(n-i)\times(n-j)+1}$。所以说这一部分的贡献是 $$\sum\limits_{1\le i\le n} \sum\limits_{1\le j\le n}\dbinom{n}{i} \dbinom{n}{j}(-1)^{i+j-1}3^{(n-j)\times(n-i)+1}$$ 接下来就是推式子了。先把与 $i$ 和 $j$ 有关的东西全部拆出来 $$\sum\limits_{1\le i\le n} \dbinom{n}{i}\sum\limits_{1\le j\le n} \dbinom{n}{j} (-1)(-1)^{i} (-1)^{j} \times 3 \times 3^{n^2} \times 3^{-in} \times 3^{-jn} \times 3^{ij}$$ 然后再整理到一起 $$ - 3^{n^2+1}\sum\limits_{1\le i\le n} (-1)^{i} \dbinom{n}{i}3^{-in} \sum\limits_{1\le j\le n} (-1)^{j} \dbinom{n}{j} 3^{-jn} \times 3^{ij}$$ 此时就剩下一个 $3^{ij}$ 比较难搞。考虑如何将他放入 $3^{-jn}$ 中 $$ - 3^{n^2+1}\sum\limits_{1\le i\le n} (-1)^{i} \dbinom{n}{i}3^{-in} \sum\limits_{1\le j\le n} (-1)^{j} \dbinom{n}{j} (-3^{i-n})^j $$ 观察后面关于 $j$ 的部分，可以用二项式定理 $(a+b)^n = \sum\limits_{0 \le i \le n} \dbinom{n}{i} a^i b^{n-i}$ 化简，将 $a=1$，$b=-3^{i-n}$ 带入。但是二项式定理会包含 $j=0$，而原式是从 $1$ 开始，也就是减去 $j=0$ 的部分贡献。这一部分的贡献就是 $1$。所以有 $$ - 3^{n^2+1}\sum\limits_{1\le i\le n} (-1)^{i} \dbinom{n}{i}3^{-in} ((1-3^{i-n})^n -1 ) $$ 这样这一部分就可以 $O(n \log n)$ 求解了。 所以最终答案是 $$2\times \sum\limits_{1\le i\le n} \dbinom{n}{i} (-1)^{i-1}3^{n\times(n-i)+i}- 3^{n^2+1}\sum\limits_{1\le i\le n} (-1)^{i} \dbinom{n}{i}3^{-in} ((1-3^{i-n})^n -1 ) $$ ::: ## 1.4 二项式反演 ### 1.4.1 公式推导 假设 $g_n$ 为在 $n$ 个元素中选 $i \ge 0$ 个元素的方案数（可能是相同，也可能是不同，根据不同情景定义的情况）。而 $f_n$ 表示恰好选 $n$ 个元素的方案。 显然可以根据 $f_n$ 来求 $g_n$。那么： $$g_n = \sum_{i=0}^n f_i \dbinom{n}{i}$$ 那如果已知 $g_n$ 该如何求？ 结论是： $$f_n = \sum\limits_{i=0}^n \dbinom{n}{i} (-1)^{n-i}g_i$$ 看起来很奇妙。尝试证明一下。 :::success[证明] 首先，先把 $g$ 带入。 得到： $$f_n = \sum\limits_{i=0}^n \dbinom{n}{i} (-1)^{n-i}\sum\limits_{j=0}^i\dbinom{i}{j}f_j$$ 整理一下： $$f_n = \sum\limits_{i=0}^n \sum\limits_{j=0}^i f_j (-1)^{n-i}\dbinom{n}{i}\dbinom{i}{j}$$ 然后考虑对于 $\dbinom{n}{i}\dbinom{i}{j}$ 这个如何化简，考虑组合意义。$n$ 个元素中选 $i$ 个，再从 $i$ 个元素中选 $j$ 个。其实等效于直接从 $n$ 中选 $j$ 个，然后，再选那些被 $i$ 包含但又没有选进 $j$ 这一类的，这一类应该是 $\dbinom{n-j}{i-j}$。 于是我们可以得到 $\dbinom{n}{i}\dbinom{i}{j} = \dbinom{n}{j}\dbinom{n-i}{i-j}$。这个结构会在一些推式子题中出现。 $$\therefore f_n = \sum\limits_{i=0}^n \sum\limits_{j=0}^i f_j (-1)^{n-i}\dbinom{n}{j}\dbinom{n-j}{i-j}$$ 移项得，再把 $i$ 和 $j$ 的遍历顺序交换一下： $$f_n = \sum\limits_{j=0}^n f_j \dbinom{n}{j} \sum\limits_{i=j}^n \dbinom{n-j}{i-j} (-1)^{n-i}$$ 在引入一个式子：根据二项式定理，所以可得：$(a+b)^n = \sum\limits_{i=0}^n \dbinom{n}{i}a^{n-i}b^{i}$。我们将 $a=-1$，$b=1$，上式就变成： $$0^n = \sum\limits_{i=0}^n \dbinom{n}{i}(-1)^{n-i}$$ 也就是： $$\sum\limits_{i=0}^n \dbinom{n}{i}(-1)^{n-i} = [n=0]$$ 再回到原始，改变一下 $i$ 的范围，得到： $$f_n = \sum\limits_{j=0}^n f_j \dbinom{n}{j} \sum\limits_{i=0}^{n-j} \dbinom{n-j}{i-j} (-1)^{n-i}$$ $$\therefore f_n = \sum\limits_{j=0}^n f_j \dbinom{n}{j} [n=j]$$ $$\therefore f_n = f_n \dbinom{n}{n} $$ $$\therefore f_n = f_n $$ 证毕。 ::: ## 1.5 范德蒙德卷积 组合推式子的技巧。 ### 1.5.1 基础公式 $$\sum\limits_{i=0}^k \dbinom{n}{i}\dbinom{m}{k-i} = \dbinom{n+m}{k}$$ 组合意义证明： 显然，即 $n+m$ 中选 $k$ 个数，然后拆成 $n$ 中选 $i$ 个与 $m$ 中选 $k-i$ 个的贡献然后乘法原理。 ### 1.5.2 简单推论 :::success[推论1] $$\sum\limits_{i=-r}^s \dbinom{n}{s-i}\dbinom{m}{r+i} = \dbinom{n+m}{s+r}$$ 即范德蒙德卷积带了个偏移量。 ::: :::success[推论2] $$\sum\limits_{i=1}^n \dbinom{n}{i} \dbinom{n}{i-1} = \dbinom{2n}{n-1}$$ 证明： $$\sum\limits_{i=1}^n \dbinom{n}{i} \dbinom{n}{i-1} =\sum\limits_{i=0}^{n-1} \dbinom{n}{i+1} \dbinom{n}{i} = \sum\limits_{i=0}^{n-1} \dbinom{n}{n-i-1} \dbinom{n}{i}$$ 由于 $\sum\limits_{i=0}^{n-1} \dbinom{n}{n-i-1} \dbinom{n}{i}$ 类似范德蒙德卷积的组合意义。$n$ 中选 $i$ 个，再在另外 $n$ 个选 $n-i-1$ 个。即共 $2n$ 中选 $n-1$ 个。即 $\dbinom{2n}{n-1}$。 ::: :::success[推论3] $$\sum\limits_{i=0}^n \dbinom{n}{i}^2 = \dbinom{2n}{n}$$ 证明同理推论2。 ::: :::success[推论4] $$\sum\limits_{i=0}^m \dbinom{n}{i}\dbinom{m}{i} = \dbinom{n+m}{m}$$ 证明： $$\sum\limits_{i=0}^m \dbinom{n}{i}\dbinom{m}{i} = \sum\limits_{i=0}^m \dbinom{n}{i}\dbinom{m}{m-i}= \dbinom{n+m}{m}$$ ::: 总结：根据以上推论发现对于 $\dbinom{n}{m}$ 转变成 $\dbinom{n}{n-m}$，然后与另一个组合数合并（前提是有一个变量可以抵消）然后就是范德蒙德卷积了。 ### 1.5.3 例题 ##### P14636 > 题目大意：给定 $n$ 个数 $a_i$ 为物品原价和 $m$ 为你的钱包。对于任意 $i$，选择设定新价格为 $b_i \in {1,2}$。以新价格来买物品。满足：贪心选（从性价比从高到低选择，即性价比为 $\dfrac{a_i}{b_i}$）是否能达到最优情况下的原价总和最大。求：满足条件的“新价格”构造方案数。 首先，正难则反。考虑贪心条件不能满足最有情况。 发现，这样的情况都有一下两种特征： :::info[性质] - 最优解会出现一个新价格为 $2$ 但是性价比较**低**，然后**贪心**的方法会选择性价比更**高**，但是原价更**低**的一个 $1$。 - 最优解选择了一个新价格为 $2$ 的。但是**贪心**会先选择一个性价比**更高**的，原价**更低**的 $1$。然后又选了一个性价比比 $2$ 还要**低**的 $1$（因为此时如果钱包剩下 $2$ ，那么先用了一个 $1$，就用不了 $2$ 了，所以还会再用一个更劣的 $1$，然而此时两个 $1$ 加起来的原价没有一个 $2$ 高）。 ::: 考虑将两种情况转换成不等式条件关系。并计算贡献。为了方便，递减排序 $a_i$。 :::success[解法] 枚举 $i$ 为**最优解**选择的 $2$，$j$ 为**贪心**选择的 $1$。 则：$\dfrac{a_i}{2} < a_j < a_i 
最优选择的方式：性价比高的**全部**选上$\{1,2,\cdots,i-1\}$，还得选枚举到的 $\{i\}$，还有在 $\{ i + 1,i+2,\cdots,j-1\}$ 中选 $1$ 的时候才会选。
贪心方式：性价比高的**全部**选上$\{1,2,\cdots,i-1\}$，还有在 $\{ i + 1,i+2,\cdots,j-1\}$ 中选 $1$ 的时候才会选。还得选枚举到的 $\{j\}$。
总的来说，贪心就是放弃了 $i$ 选择了 $j$。
再枚举一个数 $c$，表示 $[1,i-1]$ 中选择 $1$ 等数量。
那么考虑列出组合数。
性价比高的**全部**选上的方案为 $\dbinom{i-1}{c}$。
选完这些之后，还剩下 $m - (i-1+c) - 2$ 的钱。如何理解？$m$ 是总价，$i-1+c$ 已经用过的钱，$2$ 为 $i$ 所消费的钱。因此，在剩余的 $j-i-1$ 个位置中，插入 $m - (i-1+c) - 2$ 个 $1$ 。其方案就是：
\dbinom{j-i-1}{ m - (i-1+c) - 2 }

那么总方案数就是

\sum\limits_{c=0}^{i-1} \dbinom{i-1}{c}\dbinom{j-i-1}{ m - (i-1+c) - 2 }

发现 c 是变量，然而两个组合数中一加一减。就是范德蒙德卷积。所以说就可以化简为 \dbinom{j-2}{m-i-1}。这部分就结束了。

两个情况合并一下，就是：

2^{n-p+1}\dbinom{j-2}{m-i-1}

结束了吗？不。现在是 O(n^3)，考虑如何优化枚举 p。 我们发现在 j 递增的时候，p 呈单调递减，因此双指针维护 p 即可。 时间复杂度 O(n^2)。 结束了。

:::

1.6 欧拉数

1.6.1 模板

P14368

首先是这道题是欧拉数模板 \left\langle n \atop m \right\rangle 表示长度为 n 的排列恰好有 m 个 p_i > p_{i+1} 的个数（逆序对个数）。

这道题就是求 \left\langle n \atop {m-1}\right\rangle。

首先考虑通项公式，考虑从 1,\dots,n-1 放数，放到 n 时：

因此得到通项公式：

\left\langle n \atop {m}\right\rangle = \left\langle {n-1} \atop {m-1}\right\rangle \times (n-m) + \left\langle {n-1} \atop {m}\right\rangle \times (m+1)

然后 观察发现 得到：

\left\langle n \atop {m}\right\rangle =\sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k

尝试证明，利用数学归纳法，带入其通项公式得到：

:::info[证明]

\begin{array}{rcl} \left\langle n \atop m \right\rangle &=& (m+1)\sum\limits_{k=0}^m \binom{n}{k}(m+1-k)^{n-1}(-1)^k+(n-m)\sum\limits_{k=0}^{m-1} \binom{n}{k}(m-k)^{n-1}(-1)^k &(1) \\[2ex] &=& \sum\limits_{k=0}^m \binom{n}{k}[(m+1)(m+1-k)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k ]& (2) \\[2ex] &=& \sum\limits_{k=0}^m \binom{n}{k}[(m+1-k)(m+1-k)^{n-1}(-1)^k +(k)(m+1-k)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k ]& (3)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n}{k}[(m+1-k)^{n}(-1)^k +(k)(m+1-k)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k ]& (4)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n}{k}[(m+1-k)^{n}(-1)^k +(m+1-k)^{n}\frac{k}{m+1-k}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k ]& (5)\\[2ex] &=& \sum\limits_{k=0}^m (\binom{n}{k}+\binom{n}{k-1})(m+1-k)^{n}(-1)^k - \sum\limits_{k=0}^m \binom{n}{k}(\frac{k}{n+1-k}-\frac{k}{m+1-k})(m+1-k)^n (-1)^k + \sum\limits_{k=0}^m \binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k& (6)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k - \sum\limits_{k=0}^m \binom{n}{k}(\frac{k(m-n)}{(n+1-k)(m+1-k)})(m+1-k)^n (-1)^k + \sum\limits_{k=0}^m \binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k& (7)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k - \sum\limits_{k=0}^m \binom{n}{k}(m-n)(\frac{k}{(n+1-k)})(m+1-k)^{n-1} (-1)^k + \sum\limits_{k=0}^m \binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k& (8)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k - [\sum\limits_{k=0}^m \binom{n}{k-1}(m-n)(m+1-k)^{n-1} (-1)^k + \sum\limits_{k=1}^{m+1} \binom{n}{k-1}(n-m)(m-k+1)^{n-1}(-1)^k]& (9)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k - [\sum\limits_{k=0}^m \binom{n}{k-1}(m-n)(m+1-k)^{n-1} (-1)^k - \sum\limits_{k=1}^{m+1} \binom{n}{k-1}(m-n)(m+1-k)^{n-1}(-1)^k]& (10)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k - \sum\limits_{k\in{\{0,m+1\}}} \binom{n}{k-1}(m-n)(m+1-k)^{n-1} (-1)^k & (11)\\[2ex] &=& \sum\limits_{k=0}^m \binom{n+1}{k}(m+1-k)^{n}(-1)^k & (12) \end{array}

给一下解释：

$(7)$：观察到 $\dbinom{n}{k-1} = \dfrac{k}{n+1-k} \dbinom{n}{k}$。 $(8)$：$\dbinom{n+1}{k} = \dbinom{n}{k} + \dbinom{n}{k-1}$ 这是组合数通向公式。 $(9)$：尝试将后面两个和式构造成一样的。 $(11)$：观察到 $1\le k \le m$ 都是可以抵消的。 $(12)$：观察到 $k=0$ 时 $\dbinom{n}{k-1}$ 没有意义，当 $k=m+1$ 时 $(m+1-k)^n=0$，于是后面都没有贡献。 证毕。 ::: ## 1.7 第二类斯特林数 ### 1.7.1.1 基本递推公式 $S(n,k)$ 表示将 $n$ 个互不相同的元素分到 $k$ 个互不区分的非空子集的方案数。 递推式： $$S(n,k) = S(n-1,k-1) + S(n-1,k) \times k$$ 边界是 $S(n,0) = [n=0]$。 考虑一下组合意义。相较于组合数的转移： $$C(n,k) = C(n-1,k-1) + C(n-1,k) $$ 区别于后面的那一项多一个 $k$ 的系数。体现在于 $n$ 个元素是互不相同的。 其意义是： - $S(n-1,k-1)$ 表示新开一个集合放入的数，系数为 $1$。 - $S(n-1,k)$ 表示已经有 $k$ 个集合，插入这 $k$ 个集合中任意一个，系数为 $k$。 ### 1.7.2 例题 ##### CF1716F > $n$ 个袋子，其中每一个袋子放了 $m$ 个球，其中标号为 $1,2,\dots,m$，每一个袋子取出一个球。$n$ 个袋子取完之后，即 $F$ 为选出来的球编号为奇数的个数。然后求所有方案数 $F^k$ 之和。$k$ 为给定。 :::success[solution] 首先是前置式子： $$ n^m = \sum\limits_{k=0}^m \dbinom{n}{k} k! S(m,k)$$ 组合意义证明：$n^m$ 表示的是 $m$ 个两两不同的球放入两两不同的 $n$ 个盒子中的方案数（允许空集）。考虑非空集合个数为 $k$，则从 $n$ 个盒子（集合）中选 $k$ 个座位非空集合，组合数 $\dbinom{n}{k}$，又因为他是无序的，所以乘上 $k!$。然后将 $m$ 个数划分进入互补区分的 $k$ 个非空集合，即第二类斯特林数 $S(m,k)$，又因为如果 $k > m$ 则 $S(m,k) = 0$，因为失去其组合意义。所以枚举 $k$ 为 $\sum\limits_{k=0}^m$。证毕。 那么有了这个就可以开始推式子了。 设 $x$ 为奇数个数，$y$ 为偶数个数。 那么可以得到式子 $$\sum\limits_{i=0}^n i^k \dbinom{n}{i} x^i y^{n-i}$$ 由前置的式子得 $$\sum\limits_{i=0}^n \sum\limits_{j=0}^k \dbinom{i}{j} j! S(k,j) \dbinom{n}{i} x^i y^{n-i}$$ 拆开组合数得 $$\sum\limits_{i=0}^n \sum\limits_{j=0}^k \frac{i!}{(i-j)!j!} j! S(k,j) \frac{n!}{(n-i)!i!} x^i y^{n-i}$$ 再整理得 $$ \sum\limits_{j=0}^k S(k,j) \sum\limits_{i=0}^n \frac{n!}{(n-i)!(i-j)!} x^i y^{n-i}$$ 观察到那一串分数容易转换成组合数，于是 $$ \sum\limits_{j=0}^k S(k,j) \sum\limits_{i=0}^n \frac{n!(n-j)!}{(n-i)!(i-j)!(n-j)!} x^i y^{n-i}$$ 所以得到 $$ \sum\limits_{j=0}^k S(k,j) \sum\limits_{i=0}^n \frac{n!}{(n-j)!} \dbinom{n-j}{n-i} x^i y^{n-i}$$ 考虑设 $l$ 为原来的 $n-i$，且要满足 $n-i \le n-j$，所以 $l \le n-j$。于是有 $$ \sum\limits_{j=0}^k S(k,j)\frac{n!}{(n-j)!} \sum\limits_{l=0}^{n-j} \dbinom{n-j}{l} x^j x^{n-j-l} y^{l}$$ 观察到后面一串可以用二项式定理化简，则 $$ \sum\limits_{j=0}^k S(k,j)\frac{n!}{(n-j)!} x^j m^{n-j}$$ 注意到分数事实上是一个排列数所以得到最终式子 $$ \sum\limits_{j=0}^k S(k,j) n^{\underline{j}} x^j m^{n-j}$$ 可以直接递推预处理出第二类斯特林数，然后直接求上式即可。 ::: ## 1.8 子集反演 ### 1.8.1 基本模型 对于一类关于子集的问题。记有子集 $S$，$f(S)$ 为 $S$ 子集内的方案数，而 $g(S)$ 为恰好 $S$ 这个集合的方案数。 即： $$f(S) = \sum\limits_{T \in S} g(T)$$ 根据子集反演有： $$g(S) = \sum\limits_{T\in S}(-1)^{|S |- |T |} f(T)$$ :::success[证明] 将 $f$ 带入： $$g(S) = \sum\limits_{T\in S}(-1)^{|S |- |T |} \sum\limits_{Q \in T} g(Q)$$ 整理得： $$g(S) = \sum\limits_{Q\in S}g(Q)\sum\limits_{Q \in T \in S} (-1)^{|S |- |T |}$$ 记：$V = S \setminus Q$（注：$A \setminus B$ 表示属于集合 $A$ 但不属于 $B$ 的元素），即： $$g(S) = \sum\limits_{Q\in S}g(Q) \sum\limits_{T \in V} (-1)^{|V| - | T|} $$ 观察式子：$\sum\limits_{T \in V} (-1)^{| V |- |T|}$。 - 当 $V=\emptyset$ 时，即 $S = Q$，有 $\sum\limits_{T\in \emptyset} (-1)^{0} = 1$。 - 当 $V \ne \emptyset$ 时，即 $S \in Q$ 且 $S \ne Q$。则有 $\sum\limits_{T \in V} (-1)^{|V |- | T |} = 0$。证明：考虑对于一个元素 ${a} \in V$。则考虑对于有一个集合 $T \cup \{a\}$ 则会无重复无遗漏地对应一个 $T^* \setminus \{a\}$。而 $| T^* |+ 1=| T |$。则 $(-1)^{| T^* |+ 1} + (-1)^{| T|} =-(-1)^{|T|} + (-1)^{| T|} = 0$。由于两两配对，即 $\sum\limits_{T \in V} (-1)^{|V |- | T |} = 0$。 于是回到原式，当且仅当 $Q=S$ 会有贡献。 $$\therefore g(S) = g(S) \sum\limits_{T \in V} (-1)^{|V| - | T|} $$ $$\therefore g(S) = g(S) $$ 证毕。 ::: # 2 计数 Dp ## 2.1 插入 Dp 一般来说是基于排列操作。 ### 2.1.1 例题 ##### P14568 :::success[solution] 考虑插入 DP，每一次考虑 $a_i$ 插入的时候能够放在前 $i-1$ 个数之间的哪个位置。 对于 $op_i \in \{0,1\}$：确定了这个数是前面的所有数的最大值或最小值。 对于 $op_i \in \{2,3\}$：限制了后面的数都要大于或小于这个数。 在 Dp 过程中记录能够填入的空位。 $f_{i,j}$ 表示填到 $a_i$，然后可以填数的位置有 $j+1$ 个。 对于 $op_i \in \{0,1\}$：不会对后面限制，但是由于多了一个数，所以空位会多：$f_{i-1,j-1} \to f_{i,j}$。 对于 $op_i \in \{2,3\}$：会对后面有限制，所以空余位置减掉若干。所以 $\sum\limits_{j \le k\le n}f_{i-1,k} \to f_{i,j}$。 转移可以后缀和，$O(n^2)$。 ::: ## 2.2 贡献延后类 对于一些排列问题，无法在当前统计贡献，那么就让他“待统计”然后记录目前待统计的个数，然后在后面转移的时候再去结算。有点类似线段树的 LazyTag。 ### 2.2.1 例题 ##### P14364 组合技巧不难，难点在于状态设计和转移。 > 给定 $n$ 个数 $s_i$ 和 $c_i$，和 $m$。若 $s_i = 0$ 则当天的面试者一定不可以通过面试，$s_i = 1$ 只要来了面试者一定可以通过面试。对于第 $i$ 个人，若之前有 $c_i$ 个人没有面试成功，则他不会来了（即使 $s = 1$ 也没用）。问，能使至少 $m$ 通过面试的面试者排列方案。 :::success[solution] 我们发现，当前选的数，会在后面才有影响。而且记录下来肯定不可行。于是引入 **贡献延后计算**，也就是记录已经计算了多少个元素，然后剩下的在用的时候再计算。 设 $f_{i,j,k}$ 表，前 $i$ 天，$j$ 个人面试失败，其中 $c_x > j$ 的人的个数为 $k

。

转移： 当选 $c_x > j$ 且 $s_i = 1$ 即 来面试但成功。由于是填入 $c_x > j$ 根据定义应该是 $k+1$，还没有计算他的贡献，所以 $j$ 不动。所以 $f_{i,j,k} \rightarrow f_{i+1,j,k+1}

当选 c_x > j 且 s_i = 0 即 来面试但失败，可以直接计算贡献了 j \rightarrow j+1。更新当 c_x = j+1 的贡献。设 cnt_j 为 c_x = j 的数量，那么枚举 l 表示之前选的 c_x=j 的数量。所以组合数就是 \dbinom{k+1}{l}\dbinom{cnt_{j+1}}{l}l!。组合意义是在 cnt_{j+1} 个能选的中选 l 个放在 k+1 个待定的位置中，顺序不定，再乘阶乘。转移就是 f_{i,j,k} \times \dbinom{k+1}{l}\dbinom{cnt_{j+1}}{l}l! \rightarrow f_{i+1,j+1,k+1-l}

当选 c_x \le j 时，不来面试，设 pre_j 为 c_x \le j 的个数。则，原本已经有 i-k 个 c_x \le j 了，所以剩下可能被选的只有 pre_j - (i-k)，所以选一个然后更新 j+1 的贡献，和上一种情况相近。枚举 l，转移：f_{i,j,k} \times (pre_j - (i-k)) \times \dbinom{k}{l}\dbinom{cnt_{j+1}}{l}l! \rightarrow f_{i+1,j+1,k-l}

由于 l 不会超过 cnt_{j+1}，i 与 k 定时，l 总和是 n，均摊下来也就是 O(n^3) :::

2.3 贪心和分讨类

贪心一般来说是指将贪心构造的过程，转化为组合问题，去求解，分讨。

2.3.1 例题

题目源自：代码源模拟赛

对于一个序列 a = \{1,2,\cdots,n\}，a_i 代表古董的价值，对于第 i 天，小明免费获得 a_i 价值的古董（也可以选择不获得），他可以考虑卖掉它，获得 a_i 的收益，也可以留到 i+1 天（也可以无限往下留），然后 a_i = a_i + 1。小明手上最多一个古董，只有卖掉了一个才能去获取下一个。然后记 f(l,r) 为序列 [a_l,a_{l+1},\cdots,a_{r}] 的小明按贪心策略选取的最大收益。求 \sum\limits_{l=1}^n \sum\limits_{r=l}^n f(l,r)。 :::success[solution] 一道好题，实际上很简单，但是赛时被硬控 4h 而且没过，我分讨了很多种情况，然后维护多个前后缀和，和二次前后缀和，还维护了区间修 \{x,x+1,x+2,\cdots,x+len\} 这样的线段树。调的我头大。赛后膜拜了 F 先生的解法，发现十分优雅。

首先，考虑如果开头都是 a_l \ge 1 的话，那么我们发现，我们可以将 a_i \le 0 的数的贡献 a_i 设为 1。这样对于一个 [l,r] 区间的贡献就是 \sum\limits_{l\le i \le r} a_i，证明：对于所有 a_i \ge 1 的数，当然不会用到延续到 i+1 天的操作。而对于 a_i < 1 我们可以直接当作延续 i+1 天，也就是贡献为 1。

对于是 a_l < 1 的话，基本上，目的都是计算前面一部分贡献，然后再计算后面一部分贡献，后面部分的贡献就是开头 a_l \ge 1 的情况那么我们发现他会有下述情况：

我当时赛时的时候就对他们进行了分讨，这也让我维护的数据变得非常多。

然而我们发现，对于 l 的答案 f_l，是不是可以 f_l = \max(f_l ,f_{l+1})。因为如果有一个 f_{l+1} > f_l 那么显然 f_l 能够有 f_{l+1} 的贡献，这是因为我们只需要把 a_l 不选，然后留到 l+1 即可。

所以说计算 f_l 只需要考虑上述两种情况。这个是好算的。而对于后面部分 a_{l'} \ge 1 的贡献只需要开一个前缀和数组 t 记录的是 \max(1,a_i) 的前缀和，和数组 s 记录 t 的前缀和，然后套路的差分一下就行了。

另外，这一题对于 f_l = \max(f_l ,f_{l+1}) 之前不能取模，因为你要保证的是原值的最大值，而不是取模后的最大值。 :::

P6146

组合经典问题。

:::info[提示] 考虑将 $l_i$ 排序，然后如何加区间。 ::: :::success[solution] 首先是贡献继承。$f_i = 2 \times f_{i-1}$，排序了，不会减少贡献。选与不选，就是两种。考虑选了的话额外贡献，则前面如果选了 $r_j \ge l_i$ 的话，不会加贡献。所以只有选 $r_j < l_i$ 的区间才会产生贡献，记 $r_j < l_i$ 的区间个数为 $cnt_i$，则此时答案会增加 $2^{cnt_i}$（可选的区间随便选方案）。转移就是 $f_i = 2\times f_{i-1} + 2^{cnt_i}$。 :::

2.4 状态优化类

这一类问题一般难点在于构造状态。

在复杂的状态去优化。例如压缩维度，把不必要的状态去掉，换一个方向去考虑状态设计，等等。

总结了一些比较巧妙的例题。

2.4.1 例题

QOJ-9922

一个序列定义为麻将组合为：由 \{x,x,x\} 和 \{x,x+1,x+2\} 的子序列构成。给定一个序列 a 求所有区间 \{a_l,\dots,a_r\} 有多少个是麻将组合。其中 a_i \le 8，n\le 10^5。 :::success[solution] 不知道为什么赛时没有想出来，不知道为什么 jiangly 讲了半句话我就会了。首先发现，同样顺子的个数必定是 <3 的，如果 \ge 3 的那么肯定优先 \{ x,x,x\}。所以说，我们可以直接三进制状压掉除了 \{x,x,x\} 的情况剩下的每一个值出现多少次，这样的状压是 3^8 的。但是 O(3^8n) 大概会炸，考虑枚举 \{x,x,x\} 的状态，这样是 3^6 的。然后动态维护每一个状态的累计数量，然后每一次计算相当于是对于当前状态，再减去枚举的状态，就是剩下的状态就是区间左端点的差分状态。统计答案即可。 :::

P5204

求 \{a_1,a_2,\cdots,a_n\} 方案数满足 a_i \le 10^9 且对于 \{c_1,c_2,\cdots,c_{n-k+1}\} 有 c_i = \min\limits_{j=i}^{i+k-1} a_j。 :::success[solution] 我们发现如果考虑相邻的 c_i 和 c_{i+1} 如果不相等，那么可以固定一位数，一定为最小值。但是如果 c_i 连续很长的相等呢？可能甚至大于 k 这个时候对于每一个独立的连续段，做计数 DP，然后将每一段乘在一起。

考虑 sol(x,len) 表示子问题：有 len 个数，取值是 [x,10^9]，然后方案数。

先把 x 转换为 10^9 - x，这样就是选择 [0,x] 的区间了。

然后我们可以得到转移方程 dp_i = dp_{i-1} \times (x+1)。那如果超过 k 怎么办？那么就减掉从 f_{i-k-1} 之后，一直都不选下界 x，也就是 f_{i-k-1} \times x^k。

因此得到转移方程 dp_i = dp_{i-1} \times (x+1) - f_{i-k-1} \times x^k。

然后对于如何分段，随便分讨一下就出来了。 :::

P5664

三维 DP 发现有两维实际意义不大，优化成两维。

给出一个 n\times m 矩阵，要求每行只能选一个节点，每列选的节点不能超过所有选的节点的一半，不能不选，给出每个节点的选择方案数，求总方案数。 :::success[solution] 正难则反。考虑满足每行只有一个数的个数减掉有一列超过所选节点的一半的方案。

首先枚举一个 x 为超过一半节点的那一列。

设 f_{i,j,k} 是考虑到点 i，这一列选了 j，其他的选了 k。然后答案就是当 j>k 是的所有贡献。

发现 j 和 k 的具体不重要，所以设新的 j 意义为原来的 j-k。即 f_{i,j}，表示考虑到 i，这一列比其他多 j 个的贡献。然后直接线性转移。

从上往下，考虑每一行，和当前的 j。

对于这一行如果选 x 列则 f_{i-1,j-1} \times a_{i,x} \rightarrow f_{i,j}

如果不选 f_{i-1,j} \rightarrow f_{i,j}

不选 x 列，记 s_i = \sum\limits_{j=1}^{m} a_{i,j}，则 f_{i-1,j+1} \times (s_i - a_{i,x}) \rightarrow f_{i,j}

:::

P3214

奇偶的要求，可以考虑用转换为异或。

给定一个集合 S = \{1,\dots,n\}，选 m 个 S 的子集，使得 m 个子集互不相同，且对于 \forall i \in S，出现在 m 个子集中的总数量为偶数。 :::success[solution] 一开始觉得可以考虑一个 n \times m 的表格，来填。但是发现好像记录的状态比较多。互不相同也很难做。考虑转换题意。

这样来说，对于选的每一个数，相当于原题意中的子集的状态，也保证了互不相同。根据异或的性质。偶数的会抵消。所以异或和等于 0 是肯定是成对出现的。

考虑 f_i 表示选了第 i 个数，且已经异或和为 0。

考虑有多少种方式可以填进去。正难则反，总数肯定是 \dbinom{2^n-1}{i-1}，代表着之前 i-1 种情况的方案数，记前 i-1 个数异或和为 k，则 i 肯定填 k 来把 i-1 个数抵消掉，k 也是唯一对应这个方案的。

那么不合法情况呢？什么时候会选到空集（m=0）？显然当前 i-1 已经异或等于 0 了，那么你这个时候选的 k 为 0，违背了 m 不等于 0 的定义，那么这个时候的方案是 f_{i-1}。

还有，如果选到重复，也就是说 i 和 i-1 选的一样，那么就是 f_{i-2} 的时候异或和已经 0 了，然后 i-1 选了一个 x，然后 i 又选了一个 x。而 x 的个数是 2^n-1 - (i-2)，所以说这个时候的方案就是 f_{i-2} \times (2^n-1 - (i-2))。

然后又因为每一个 i 会重复选 i 次。所以初一 i 即可。

得到转移方程 f_i = \dfrac{\dbinom{2^n-1}{i-1} - f_{i-1} - f_{i-2} \times (2^n-1-(i-2))}{i} :::

2.5 容斥类

2.5.1 容斥基本公式

对于三个集合 A，B，C 的并集，小学一年级就知道我们可以这样表示：

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B|- |A \cap C| - |B \cap C| + |A\cap B \cap C|

这种以元素个数的 奇偶性 来考虑加减的问题。统称为 容斥。

推广即：

|\bigcup\limits_{x\in S} x| = \sum\limits_{T \in S} (-1)^{|T| - 1} |\bigcap\limits_{y \in T} y|

2.5.2 例题：基于基础容斥的应用

AGC036F

给定一个整数 N。请计算满足以下条件的 (0,1,\cdots,2N-1) 的一个排列 (P_0,P_1,\cdots,P_{2N-1}) 的个数。条件：对于所有 i\ (0\leq i\leq 2N-1)，都有 N^2 \leq i^2 + P_i^2 \leq (2N)^2。(N \le 250)。 ::::success[solution]

跟着 CSP2025 员工招聘找过来的。

先吧每一个 i 可以填的 P_i 上下界 [L_i,R_i] 打表出来，发现是两个四分之一圆。然后下限圆的半径是 n，上限的半径是 2n。

有个题解说的很好，这个就是两个弧为区间，做“互不侵犯”，很有道理。得放入不同行不同列。 :::info[图片] ::: 那么如果说没有下限的限制。是一个很板的做法。就是按照上限从小到大排序。然后每一次从当前的段选一个点。下一个段就会少选一个，答案就是 \prod_{i} r_i -(i-1) 这么一个东西。

那么对于这题有下限，而且上限下限都在变。难搞，能不能直接不管下限，只考虑上限，然后来做容斥？

那么容斥的系数为 k 即选了 k 个不合法（在下限以内）的答案为 f(k)。

那么最后的答案就是 \sum\limits_{k=0}^n (-1)^k f(k)。

首先枚举 k，考虑如何求 f(k)。

而这题的关键是给 2n 个上下限排序。

我们发现 [n,2n) 的数都是 l_i = 0，不妨钦定 [0,n) 的数为 第一类，[n,2n) 的数为 第二类。

那么如果是第二类的话，他们不会影响不合法情况，就按照 r_i 为第一关键字排序，如果是第一类的话，可能会进入不合法的情况，要考虑容斥，所以以 l_i - 1 为第一关键字排序，也就是说不合法的那个圆的上限。

记 dp_{i,j} 表示前 i 个数，j 个不合法的方案数。

当考虑加入第 i 个数的时候，设 x 为之前 l_z=0 的个数，y 为之前 l_z > 0 的个数。

然后就做完了。时间复杂度是 O(n^3)。又是一个很有意思的数数题。 ::::

P7670

:::success[solution] 观察到一个性质，对于每一个串 T，他的长度是 L，但是其中字符 1，0，? 的个数分别是 a，b，c，则有 \min(a,b,c) = \frac{L}{3}。

所以考虑分类讨论：

这样时间复杂度 O(Q \times 2^{\frac{L}{3}})。 :::

2.5.3 Min-Max 容斥

这是一类容斥方式。

2.5.3.1 基本模型

对于一个集合 S。

令 \max(S) = \max\limits_{x\in S} x 和 \min(S) = \min\limits_{x\in S} x。

会有一个结论：

\max(S) = \sum\limits_{T \in S} (-1)^{|T|-1}\min(S)

考虑证明：（参考 OIWIKI）。

:::success[证明]

记有 x \in S 且为集合中第 k 小，令 f(x) = \{1,2,\dots,k\}。

那么显然会有 f(\min(x,y)) = \{1,2,\dots,\min(x,y)\} = f(x) \cap f(y)。

同理得 f(\max(x,y)) = \{1,2,\dots,\max(x,y)\} = f(x) \cup f(y)。

推广可以得到：

|f(\max\limits_{i\in S} x_i)| = |\bigcup\limits_{i \in S} f(x_i)|

所以根据容斥原理的基本公式得到：

=\sum\limits_{T\in S} (-1)^{|T|-1} |\bigcap\limits_{i \in T}f(x_i)|

而里面的交集就是 \min，带入得到：

= \sum\limits_{T\in S} (-1)^{|T|-1} |f(\min\limits_{j\in T} x_j)|

而 x 与 f(x) 是一个双射关系，所以映射回去即可。

证毕。 ::: 然而这个式子是可以推广到概率上或者第 k 大小上的。通常来说，求最大最小的概率或者期望是比较困难的。所以就可以用这个式子来求。

2.5.3.2 推广至期望问题

上述公式推广到期望问题也是可行的。这也使得一些难求的期望最值问题可以通过它来求。

结论是：

E(\max_{i\in S} x_i) = \sum\limits_{T \in S} (-1)^{|T|-1}E(\min_{j\in T} x_j)

:::success[证明]

参考自 OIWIKI。

考虑如何求一个 S 的期望，显然有：

E(\max\limits_{i\in S} x_i) = \sum\limits_{y} P(y=x) \max\limits_{y \in S} y_j

也就是对于所有的有概率 P(x=y) 与 x 相等的 y，他的 \max 的 \sum 就是期望的最大值。

那么为什么这个期望也满足原式呢？

考虑将他带入：

E(\max\limits_{i\in S} x_i) = \sum\limits_{y} P(y=x) \max\limits_{y \in S} y_j

就会有：

= \sum\limits_{y} P(y=x) \sum\limits_{T \in S} (-1)^{|T|-1}\min_{j\in T} y_j = \sum\limits_{T \in S} (-1)^{|T|-1}\sum\limits_{y} P(y=x)\min_{j\in T} y_j

对，后面这一坨不就又是这个期望吗。

所以得到：

= \sum\limits_{T \in S} (-1)^{|T|-1} E(\min_{j\in T} x_j)

证毕。

:::

2.5.3.3 拓展 Min-Max 容斥

\text{kthmax}_{i\in S} x_i = \sum\limits_{T \in S} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min\limits_{j\in T} x_j \text{kthmin}_{i\in S} x_i = \sum\limits_{T \in S} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}\max\limits_{j\in T} x_j E(\text{kthmax}_{i\in S} x_i )= \sum\limits_{T \in S} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min\limits_{j\in T} x_j) E(\text{kthmin}_{i\in S} x_i )= \sum\limits_{T \in S} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\max\limits_{j\in T} x_j)

:::success[证明]

钦定 \forall 1\le i < n, x_i \le x_{i+1}，那么枚举每一个 i \in S,x_i 作为第 k 小的贡献。得到：

\sum\limits_{T \in S} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min\limits_{j\in T} x_j=\sum\limits_{i\in S} x_i \sum\limits_{T \in S} (-1)^{|T| - k}\dbinom{|T|-1}{k-1} [x_i = \min\limits_{j\in T} x_j]

令枚举 j 为 |T|，把枚举 T 然后 \min 的布尔值转换成组合形式，则：

=\sum\limits_{i\in S} x_i \sum\limits_{j = k}^n (-1)^{j - k}\dbinom{n-i}{j-1}\dbinom{j-1}{k-1}

发现这个组合形式有传递性即 \dbinom ab \dbinom bc = \dbinom ac \dbinom{a-c}{b-c}，化简得：

=\sum\limits_{i\in S} x_i \sum\limits_{j = k}^n (-1)^{j - k}\dbinom{n-i}{k-1}\dbinom{n-i-k+1}{j-k}

将 j \to j-k，然后发现 \sum 中 n-i-k+1 < j \le n-k 中没有意义，所以上限调整到 n-i-k+1，得到：

=\sum\limits_{i\in S} x_i \dbinom{n-i}{k-1} \sum\limits_{j = 0}^{n-i-k+1} (-1)^{j}\dbinom{n-i-k+1}{j}

然后发现 \sum\limits_{j = 0}^{n-i-k+1} (-1)^{j}\dbinom{n-i-k+1}{j} 是二项式定理，带入 -1 得到：

\sum\limits_{j = 0}^{n-i-k+1} (-1)^{j}\dbinom{n-i-k+1}{j} = (1 + (-1) )^n = 0^n

所以当且仅当 n-i-k+1 = 0 （即 i = n-k+1）时，

\sum\limits_{j = 0}^{n-i-k+1} (-1)^{j}\dbinom{n-i-k+1}{j} = 1

否则其为：

\sum\limits_{j = 0}^{n-i-k+1} (-1)^{j}\dbinom{n-i-k+1}{j}= 0

所以说只有 i=n-k+1 时才有贡献，即第 k 大时有贡献。

所以：

= \text{kthmax}_{i\in S} x_i

证毕。

同理得：\text{kthmin} 证明类似。期望证明也是简单的。

:::

2.5.3.4 例题

P4707

首先前置是拓展 Min-max 容斥。

:::success[solution]

E(\text{kthmax}(S))= \sum\limits_{T\in S} \dbinom{|T| - 1}{k-1} (-1)^{|T|-k} E(\min(T))

考虑题目求的是实际上是：

E(\text{kthmin}(S))

但是 n-k \le 10，于是不妨令 k=n-k+1，转换题意为：

E(\text{kthmax}(S))

也就是：

\sum\limits_{T\in S} \dbinom{|T| - 1}{k-1} (-1)^{|T|-k} E(\min(T))

当然肯定不能直接枚举 T，于是考虑 Dp。

Dp 过程维护每一个元素，以及当前放入 T 中的状况。

令 f_{i,j,l} 为枚举前 i 个元素，其中在 T 中的 p_x 有 \sum p_x = j，记录：

f_{i,j,l} = \sum\limits_{i\in T} \dbinom{|T|-1}{l-1} (-1)^{|T|-l}

考虑两种转移情况：

其中 T 不含 i，那么 f_{i-1,j,l} \to f_{i,j,l}。

如果 T 中包含 i，那么考虑 x-1 的时候的 f_{i-1,?,?} 为：

\sum\limits_{T} \dbinom{|T|}{l-1} (-1)^{|T|-l+1}

又因为 \dbinom{n}{m} = \dbinom{n-1}{m-1} + \dbinom{n-1}{m} 这个递推式。

所以有：

\sum\limits_{T} \dbinom{|T|}{l-1} (-1)^{|T|-l+1} = \sum\limits_{T} (\dbinom{|T|-1}{l-2}+\dbinom{|T|-1}{l-1}) (-1)^{|T|-l+1} = \sum\limits_{T} \dbinom{|T|-1}{l-2}(-1)^{|T|-l+1}+\sum\limits_{T}\dbinom{|T|-1}{l-1} (-1)^{|T|-l+1} = \sum\limits_{T} \dbinom{|T|-1}{(l-1)-1}(-1)^{|T|-(l-1)}-\sum\limits_{T}\dbinom{|T|-1}{l-1} (-1)^{|T|-l}

将它转换成 Dp 式，即：

=f_{i-1,j-p_i,l-1}-f_{i-1,j-p_i,l}

综上，得到转移方程：

f_{i,j,l} = f_{i-1,j,l} + f_{i-1,j-p_i,l-1} - f_{i-1,j-p_i,l} 最后答案就是： $$\sum\limits_{j=1}^m \dfrac{m}{j}f_{n,j,k}$$ ::: ## 2.6 插头 Dp 插头 DP。其核心思想是，利用状压维护轮廓线的状态进行 Dp 转移。 模板题：[https://www.luogu.com.cn/problem/P5056](https://www.luogu.com.cn/problem/P5056)。 ### 2.6.1 定义 ![](https://cdn.luogu.com.cn/upload/image_hosting/zq30brte.png) 这是一个 $8 \times 5$ 的网格，其中蓝线代表其中一条回路。我们暂且不考虑其 **障碍**。 记当前从左到右，从上往下枚举，枚举到的为图中绿色格子 $(4,4)$，则有： - 轮廓线：为红色的一条 **线**，其作用是区分 **已枚举** 与 **未枚举** 部分的分割线。 - 插头：为了满足回路性质，一个格子有两个插头，对应的是四个方向其中的两个在回路图上的出度和入度。具体地，如格子 $(2,2)$ 就有两个插头，分别为右插头和下插头。 ### 2.6.2 状态设计 ![](https://cdn.luogu.com.cn/upload/image_hosting/dk9op6l1.png) 考虑对回路赋予方向。其中橙色的箭头代表着回路走到方向。 考虑用状态去记录 **轮廓线** 与 **回路** 相交的关系。 容易发现： - 箭头向下：代表着 **已枚举** 的部分穿过 **轮廓线** 向 **未枚举** 的部分走。记为 $1$。 - 箭头向上：代表着 **未枚举** 的部分穿过 **轮廓线** 向 **已枚举** 的部分走。记为 $2$。 - 没有箭头：代表着 **轮廓线** 没有与回路有交点，即为 $0$。 那么我们就可以赋予上图中轮廓线的状态：$(121002)_3$。可以用三进制表示。 **重点**：状态记录的方式实际上是 **括号序列**。 即，状态中的 $1$ 和 $2$ 是满足 **括号匹配** 的。 ![](https://cdn.luogu.com.cn/upload/image_hosting/zsa029k6.png) 若一个轮廓线上从左到右 $a,b,c,d$ 四个点，若 $(a,c)$ 是联通的，即从 $a$ 往下走，然后从 $c$ 又往上走回去。那么 $(b,d)$ 肯定不能联通。可以理解为被 $(a,c)$ 挡住，感性证明一下。 当然这个所谓的 **方向** （即 $1$ 和 $2$）实际上是相对的，而并非绝对的。他是在维护的过程中改变的，只要满足括号匹配原则即可。 ### 2.6.3 状态转移 $dp_{i,j,s}$ 代表枚举到点 $(i,j)$，其轮廓线状态（一个三进制数） $s$ 的方案数。 发现每一次转移只与上一次的轮廓线状态有关系。所以前两维可以优化掉。所以可以设计新状态 $dp_{now,s} ,now \in \{0,1\}$。 记当前枚举的 $(i,j)$ 点的左插头情况为 $x$，上插头情况为 $y$。如果插头存在则为 $1$ 否则为 $0$。 大体上可以分为 $7$ 中转移方式。 :::info[Type 1] 若 $(i,j)$ 为障碍。则其必须在 $x=y=0$ 时才可以转移。 ![](https://cdn.luogu.com.cn/upload/image_hosting/x3myxev9.png) ::: :::info[Type 2] 若 $x=y=0$ 且 $(i,j)$ 不是障碍。 此时 $(i,j)$ 的右插头和下插头必须存在。于是创建其右插头和下插头。 条件是 $(i+1,j)$ 和 $(i,j+1)$ 必须是非障碍格子。 所以在新的轮廓线（图中红色虚线）上，要加上 $1$ 和 $2$。（意义是这是一对括号，即一进一出）。而且 $1$ 要在 $2$ 前面，$1$ 对应的是左括号，$2$ 对应的右括号。 ![](https://cdn.luogu.com.cn/upload/image_hosting/848iu124.png) ::: :::info[Type 3] 当 $x=1$ 且 $y=0$ 时，那么 $(i,j)$ 已经有一个插头了，所以需要考虑新建一个插头。新插头可以作为右插头或者下插头。分两种情况讨论。 判断条件依然同上是，新建下插头时 $(i+1,j)$ 必须非障碍。新建右插头时 $(i,j+1)$ 必须为非障碍。 ![](https://cdn.luogu.com.cn/upload/image_hosting/d86hbkkg.png) 当然，图中新轮廓线的 $1$ 和 $2$ 都可以，根据原先轮廓线。是要与原先轮廓线相同的。 ::: :::info[Type 4] 当 $x = y = 1$，即条线合并了。所以两个 $1$ 类点会消失。不再需要记录他在轮廓线上的信息。所以根据括号匹配原则，后面会存在两个 $2$（右括号），于是将他们变成新的一对括号，修改左边的 $2$ 成为 $1$。 具体地，将 `(())` 变成了 `..()`。 ![](https://cdn.luogu.com.cn/upload/image_hosting/nbqv9hd2.png) ::: :::info[Type 5] 当 $x=y=2$ 时，同理上一种情况可得，左边的第一个 $1$ 会变成 $2$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/vdzs7a60.png) ::: :::info[Type 6] 当 $x=2$ 且 $y=1$ 时，合并了并不会对其他点造成影响，合并即可。 具体地，可以看作是 `()()` 到 `(..)`。 证明：由于括号匹配原则，$x$ 前必定有一个 $1$，$y$ 后必定 $2$，于是删掉 $x$ 和 $y$ 后括号匹配依然成立。 ![](https://cdn.luogu.com.cn/upload/image_hosting/q74vaskb.png) ::: :::info[Type7] 当 $x=1$ 且 $y=2$ 时。 若当前不是最后一个非障碍点。那么他会是一个连通分量形成闭环，那么剩余未处理得非障碍点就会与目前的这个连通分量 **不连通**，违背了回路得要求。 于是此时当且仅当 $(i,j)$ 为最后一个处理的非障碍点，才能够合并。而合并了就结束了。所以在此时记录答案。 ![](https://cdn.luogu.com.cn/upload/image_hosting/51ksihov.png) ::: 至此，所有的转移结束。代码稍微有一些细节。 发现转移的状态并不会很多，所以我们可以用一个 map 储存即可。 ### 2.6.4 总结 插头 Dp 适合解决数据范围较小的网格含障碍的 **回路** 问题。利用了巧妙地轮廓线状态，将 $O(n\times m\times 2^{n\times m})$ 的时间复杂度优化到 $O(n\times m^2 \times 2^{m})$ 级别的。是状压一种非常人类智慧的做法。 模板题的多倍经验：P2289，B4299。 插头 Dp 注意事项：状态数量有可能会因为行数过大然后每一次位移扩大。所以每一次特判掉过大的状态，如 $> 3^{13}$。 模板代码见：[https://www.luogu.com.cn/article/lnt1ee7l](https://www.luogu.com.cn/article/lnt1ee7l)。 ### 2.6.5 例题 ##### P5074 与模板不同的是，本题可以存在多个不互相联通的回路。 :::success[solution] 很简单，模板中约束着只有一个联通分量，是在其“Type 7”，第七类转移方式，即 $(i,j)$ 左插头为 $1$，右插头为 $0$ 时，当且仅当是最后一个非障碍点才能转移。 而这里不一样，它可以多个联通分量，所以即使不是最后一个非障碍节点也是可以可以转移。可以参考模板题画的图。 ::: ##### P3190 找的是最大 $\sum$ 回路。 :::success[solution] 实际与模板不同的就是 Dp 过程中不是统计 $\sum$，而是取 $\max$。而本题又允许可以不选一些格子，而且必须是唯一连通分量。 所以对于每一个格子，当他的左插头和上插头为 $0$ 的时候就可以不选，（等效于模板中的障碍点）。 另外，统计答案不是到最后一个点再统计，因为不一定选满，所以判断如果有一个点左插头为 $1$，右插头为 $2$，然后其他位置的插头都是 $0$，这个时候才可以统计答案。 ::: ##### P1713 求的固定起终点的不交叉路径的权最大值和最小值。 :::info[提示] 最小值好求，BFS 即可。 考虑如何求最大值。 考虑如何把这条固定起终点的路径 **补全** 成一条回路。然后做插头 Dp。 ::: :::success[solution] 如图：以样例举例。 ![](https://cdn.luogu.com.cn/upload/image_hosting/71ijecax.png) 可以在原图右下，补两行，使他成为一个回路。 然后只统计经过 $(n+2,n+2)$ 的回路最大值。 算答案的时候减去绿色部分的即可。 ::: ##### P6493 与 P1713 是同理的。 ## 2.7 连续段 Dp 比较巧妙的 trick，适合解决一些排列问题。 具体过程直接看例题吧。 ### 2.7.1 例题 ##### P9197 :::success[solution] 这道题比较有意思。 发现有一篇文章总结了关于这一类基于处理状态依赖相邻的排列计数问题。 [https://www.cnblogs.com/chroneZ/p/17938137](https://www.cnblogs.com/chroneZ/p/17938137) 回到本题，实际上就是在一个坐标系上以任意顺序放置点。然后是的点之间连线，线长度小于等于 $L$。具体地，画图可以看 [https://www.luogu.com.cn/article/q5xlnas2](https://www.luogu.com.cn/article/q5xlnas2)。 这里借用他的用一下。（感谢![](https://cdn.luogu.com.cn/upload/image_hosting/dzez98mv.png) 将 $a$ 从大到小排序后，考虑依次插入 $a_i$。同时，目前统计的答案都是红色的那些线段。 然后向下扫的时候，加入了一个点 $a_i$。 他有可能会是两条红线的交点，也有可能沿着这个红线，也可能新开一条红线。 那么，我们可以维护目前状态下，红线正在往下延长的有多少个。其实就是图中绿线部分。 延长的个数，就是值域每往下 $-1$，会给答案累计的偏移量。 但是，还得考虑头尾的两个数有没有被加入。 所以可以设计状态 $f_{i,j,0/1,0/1}$，$i$ 表示加入数 $a_i$，$j$ 表示目前累积的答案已经有 $j$，头尾两个是否被加入。 这样，我们就有这几种方式去转移： - $f_{i,j-1,0/1,0/1} \to f_{i,j,0/1,0/1}$ 新开了一个线段。 - $f_{i,j,0/1,0/1} \to f_{i,j,0/1,0/1}$ 延续一条线段继续往下。 - $f_{i,j+1,0/1,0/1} \to f_{i,j,0/1,0/1}$ 将两条线段合并。 具体地，转移方程系数和细节不必过多阐述。 ::: ##### P5999 :::success[solution] 本题用到与 P9197 一样的 trick。即插入排列的连续段 Dp。 发现实际上就是一个排列 $p$，然后对于每一个 $p_i$ 要么都大于左右两个，要么都小于左右两个。 考虑数从小到大加入，如果他不是 $s$ 或 $t$，那么他只要插入在两个数之间，那肯定合法的。他直接比两边的大了。或者是，他选择新建一个连续段。 于是 $f_{i,j}$ 表示枚举到 $i$，连续段 $j$ 个数。 - 新建：上一个状态 $j-1$ 段，所以有 $j$ 个位置给他新建，又由于 $s$ 与 $t$ 锁死在开头结尾。所欲位置个数是 $j-[i>s]-[i>t]$。$f_{i-1,j-1} \times (j-[i>s]-[i>t]) \to f_{i,j}$。 - 插入：上一个状态 $j+1$ 段，目前 $j$ 个位置给他插，$f_{i-1,j+1} \times j \to f_{i,j}$。 如果他是 $s$ 或 $t$ 那么 $f_{i-1,j-1} + f_{i-1,j} \to f_{i,j}$。 ::: ##### P10547 ::::success[solution] 考虑转换题意。 注意到，$m$ 次还原等价于 $\sum |i-p_i| \le 2m$。 :::info[证明] 证明： - 必要性显然，对于一次交换 $i$ 与 $j$，即从 $|p_i - i| + |p_j - j| \to |p_i - j| + |p_j - i|$，显然有 $(|p_i - i| + |p_j - j|) - (|p_i - j| + |p_j - i|) \le 2 |i - j|$。推广到全局即 $\sum |i-p_i| \le 2m$。 - 充分性显然，对于一个没有完成排序的排列 $p$，肯定会有一个 $(i,j)$ 使得 $p_j \le i < j \le p_i$，考虑对于 $\min p_j$ 满足 $p_j < j$。此时会使得对于所有 $1\le k<p_j$ 的 $p_k = k$。此时忽略所有 $\le k$ 的 $p_k$，$p_j$ 作为最小的 $p_j < j$，所以肯定可以有一个 $p_j \le i < j \le p_i$。此时找到 $(i,j)$ 并对其做 **交换** 即可。 ::: 考虑每一次交换的操作，要么会将两个置换环合并，要么会将一个置换环分裂，所以说，经过 $n$ 次交换后，置换环个数一定是偶数。 又因为 $\sum |i-p_i| \le 2m$。 所以 $\sum [i < p_i](p_i - i) \le m$。 所以基于置换环的奇偶性和升边（$p_i - i$）的贡献 $\sum p_i-i$ 做 Dp。 考虑 $f_{i,j,k,l}$ 表示考虑前 $i$ 个数，链个数 $j$，升边贡献为 $k$，$l$ 环（置换环）的奇偶性为 $l$。 可以得到转移方程： - 新建一条链，此时 $j+1$，然后维护升边目前加的贡献就是 $j$：$f_{i,j,k,l} \to f_{i+1,j+1,k+j,l}$。 - 新建一条链，并且为自环，不同于上面的是，环的奇偶性改变：$f_{i,j,k,l} \to f_{i+1,j+1,k+j,!l}$。 - 接在某一条链的前面或后面，方案为 $2\times j$：$f_{i,j,k,l}\times 2\times j \to f_{i+1,j,k+j,l}$。 - 合并两条链，其方案为 $j \times (j-1)$：$f_{i,j,k,l}\times(j-1)\times j \to f_{i+1,j-1,k+j,l}$。 - 加入一条链，使其变成环，方案为选一条链 $j$，环奇偶性反转：$f_{i,j,k,l}\times j \to f_{i+1,j-1,k+j,!l}$。 多测的话，可以只跑一遍，记录查询，然后在 Dp 的过程中记录即可。 :::: # 3 概率类 其实概率与计数类似，都是数数题。于是归类到本文。 ##### P5104 :::success[solution] 基础题。 第一个人期望是 $\dfrac{w}{2}$。 第二个人期望应该是原先剩余的前，再除以 $2$，即 $\dfrac{w}{2}$。 所以答案即 $\dfrac{w}{2^k}$。 ::: ##### P4550 :::success[solution] 选到 $i$ 个不同的数，则选到新的就是 $\dfrac{n-i}{n}$ 概率，那么多少次才能选到？它的期望就是 **概率的倒数** 即 $\dfrac{n}{n-i}$，而价格就是期望的次数。然后遍历一遍 $i$ 即可。 ::: ##### QOJ-15309 > $p$ 为 $\{1,2,\dots,n\}$ 的排列。$f(p)=\{i \ |\ 1\le i\le n,\forall j<i | p_i > p_j \}$，$g(p)=\{p_i \ |\ 1\le i\le n,\forall j<i | p_i > p_j \}$。给定 $k$ 个长度为 $k$ 的随机排列 $p$，求出现本质不同的 $g(p)$ 的期望个数。 :::success[solution] 由于 $p$ 为排列，显然 $g(p)$ 本质不同个数等效于 $f(p)$ 本质不同个数。所以实际上求 $f(p)$ 本质不同的期望即可。 考虑 $i$ 在 $f(p)$ 中出现，则 $\max(\{p_1,\dots,p_i\}) = p_i$，由于是排列，所以对于 $\forall j < i$ 的 $ p_j = \max(\{p_1,\dots,p_i\})$ 概率是一样的，所以 $p_i = \max$ 概率为 $\dfrac{1}{i}$，不为 $\max$ 的概率就是 $\dfrac{i-1}{i}$。 所以考虑有 $t$ 个排列的 $f(p)$ 不同，则期望应该为 $\prod\limits_{i=1}^n ((\dfrac{1}{i})^t + (\dfrac{i-1}{i})^t)

。枚举的每一个 i 代表这一个数 都出现 或者 都不出现 的概率。然后乘法原理求积即可。

然后再枚举 t，组合意义一下得：注意，还得容斥，因为会重复。

\sum\limits_{t=1}^k (-1)^{t-1}\dbinom{k}{t}\prod\limits_{i=1}^n ((\dfrac{1}{i})^t + (\dfrac{i-1}{i})^t)

首先注意到，若 E_u 表示边 (\text{father}_u,u) 为重边的概率，那么概率是可以叠加的，所以答案为 \sum\limits_u (1-E_u) \times \text{size}_u。 :::

P15649

:::success[solution] 第一感觉是可以 O(n)，但是，用每一个边的重边期望去算其重儿子期望 是错的。因为重儿子期望是基于多个边的重边期望，多个重边期望之间也是互相影响的，不能直接盲目叠加。所以不能直接 O(n) 的从下往上推。

考虑正解，记 p_{u,i} 表示节点 u 为链首，链长度为 i 的 期望，g_{u,i} 表示节点 u 的 兄弟们 为链首的所有链长度 总和 为 i 的期望。

所以对于 E_u 就可以有 E_u = \sum\limits_{v\in \text{son}_u} g_{v,i}\times p_{v,j} \times \frac{j}{i+j}。意义为，当子树内链长总和为 i+j 时，选到 v 的概率，然后概率的累加即可。

那么考虑如何维护 p 和 g 然后就能处理出 E，就能算出答案。

再记 f_{u,k} 表示 u 的儿子中，重链长度总和为 k 的概率。

可以根据 p 和 g 得到 f：

f_{u,l} = \sum\limits_{0\le k\le l} \sum\limits_{v\in \text{son}_u} p_{v,k} \times g_{v,l-k}

将 g_{v,l-k} 充当为未知数，考虑通过 p 和 f 求出 g。

由于 k 是有一个下限的，也就是说找到最大的 k 满足 \forall i,i < k,p_{u,k} =0。换句话说 k 是第一个有用的 p。

那么把 l 作为 i+k。

所以有：

提出 j=k 项：

移项：

仔细观察这个式子，发现这好像像背包。f 是 p 与 g 的总贡献，枚举的 k < j \le i+k-1 是一段连续的 物品 不要拿。然后剩余物品的贡献。

然后这个 trick 就叫做 退背包 顾名思义，即每一次维护的 不取 一些物品的背包贡献。

然后 p，f，g 维护不难。可以做到 O(n^2)。

:::

ARC217C

:::success[solution]

笑话：其实是场切了。由于在最后一分钟调出来，然后提交，发现 CE，没有时间修改了。然后发现竟然是我在复制代码的时候不小心删掉了一个字符。

进入正题。

考虑将每一个物品 a_i 放到区间上。[1,C] 的区间上有很多个段 [a_{i-1},a_i]，当不考虑之前是否选过。一个价格 x 落在 [a_{i-1},a_i] 区间的概率就是 i 商品被选的概率。

那么我们可以去求 f(m) 表示至少选 m 个商品的方案。然后每个答案就是 f(m)-f(m+1)。

于是枚举 m 去算 f(m) 即可。

考虑如何求每一个 f(m)：钦定 p_i = \dfrac{a_i - a_{i-1}}{C} 即商品 i 被选中的概率。

设 dp_{i,j} 表示大到小考虑到第 i 个商品，目前已经有 j 个物品被选中。

考虑去枚举 i 这一段被连续选了 k 次，然后他就会顺势在 i 往前选 k 个，这个可以不被关注。这个的概率 (p_i)^k，由于 k 是从 j 里选的，所以要组合数。

然后可以得出转移方程：

dp_{i,j} = \sum\limits_{0\le k\le j} \binom{j}{k} (p_i)^k dp_{i-1,j-k}

那么 m 又有什么用？

他约束着必须至少选 m 个，所以在转移过程中，如果枚举的 j 有 j \le m-i 那么 dp_{i,j} 不是合法方案，设为 0。

然后时间复杂度是 O(n^4)，实际上是 5 \times 10^7 可以通过。 :::

参考文献

(参考的太多了，仅放了部分优质，较大参考意义的文章)。

https://oiwiki.com/math/combinatorics/vandermonde-convolution/ https://oiwiki.com/math/combinatorics/combination/ https://www.luogu.com.cn/article/mywr0ju7 https://www.luogu.com.cn/article/e5jzfdyn https://www.luogu.com.cn/article/l51b16so https://www.luogu.com.cn/article/zolp6r1a https://www.luogu.com.cn/article/jvpd8zra https://www.luogu.com.cn/article/r3jp3ckf https://www.luogu.com.cn/article/zlg0rx0k https://www.luogu.com.cn/article/hgxv0e2v https://www.luogu.com.cn/article/qsphvygu https://www.luogu.com.cn/article/ro6a92sp https://www.luogu.com.cn/article/hypndkiz https://www.luogu.com.cn/article/q5xlnas2 https://www.cnblogs.com/chroneZ/p/17938137 https://www.luogu.com.cn/article/xt2szowt --好文 https://www.luogu.com.cn/article/a47k0ffs