分享.tex
yes_NT
·
·
闲话
\documentclass[table]{beamer}
\usepackage[UTF8, noindent]{ctexcap}
\usetheme{Berlin}
\usecolortheme{default}
\title{计数类DP题选讲}
\author{yes\_NT}
\date{2026.1.25}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\section{CF1842G}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1842G}{CF1842G}}
给定一个长度为 $n$ 的数组 $a$ 和一个整数 $v$。
将进行 $m$ 次如下操作：
1. 每次等概率随机选择一个整数 $i$，满足 $1 \leq i \leq n$。
2. 对所有满足 $i \leq j \leq n$ 的 $j$，将 $a_j$ 赋值为 $a_j + v$。
经过 $m$ 次操作后，$\prod_{i=1}^n a_i$ 的期望值是多少，结果对 $10^9+7$ 取模。
$1\leq n\leq 5000$，$1\leq m,v\leq 10^9$，$1\leq a_i\leq 10^9$
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1842G}{CF1842G}}
组合意义保平安。
$\prod_{i=1}^n a_i$ 的组合意义是从 $0$ 出发走到 $n$ 的路径条数。一次操作相当于从走到 $i$ 这个点开始，增加一次选择 $v$ 种的机会。
可以把修改当做在这个点放下了一个工具，走到的时候可以捡起来。
记 $f_{i,j}$ 表示考虑了前 $i$ 个位置，走过的路径中已经使用了 $j$ 个修改的方案数。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1842G}{CF1842G}}
1.走过 $a$
$f_{i+1,j}\gets f_{i,j}\times a_{i+1}$
2.走过已经用过的一个修改
$f_{i+1,j}\gets f_{i,j}\times j\times v$
3.走过没有用过的修改，需要知道这个修改的开始位置
$f_{i+1,j+1}\gets f_{i,j}\times (i+1)\times (m-j)\times v$
答案为 $\frac{\sum f_{n,i}\times n^{m-i}}{n^m}$
\end{frame}
\section{P7154}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7154}{P7154}}
给定 $N$ 个牛棚的大小为 $t_1,t_2,…,t_N$，奶牛的大小为 $s_1,s_2,…,s_N$。
奶牛 $i$ 可以睡在牛棚 $j$ 中当且仅当她的大小可以进入牛棚（$s_i\le t_j$）。每个牛棚中至多可以睡一头奶牛。
我们称奶牛与牛棚的一个匹配是极大的，当且仅当没有任何一对未匹配的奶牛和牛棚满足条件。
计算极大的匹配的数量模 $10^9+7$ 的结果。
$1\le N\le 3000$，$1\le s_i,t_i\le 10^9$
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7154}{P7154}}
考虑将 $s$ 和 $t$ 从小到大排序，扔到同一个序列。对于每个 $t_j$ ，能匹配的 $s$ 会是一个前缀。
这样可以考虑到，如果我们钦定某一个 $s_i$ 不加入匹配，那么在这个位置之后的所有 $t_j$ 都不能加入匹配。
因此，我们需要知道，到达某一个 $t$ 时，前面的 $s$ 是否都加入匹配。由于要记录方案，我们还需要知道这个 $t$ 和哪一个 $s$ 匹配，记 $f_{i,j,0/1}$ 表示考虑到位置 $i$（对于 $s$ 和 $t$ 在一起的序列），已经加入了匹配，但是没有确定和哪个 $t$ 匹配的 $s$ 的个数为 $j$，当前前缀的 $s$ 是否全部加入匹配。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7154}{P7154}}
如果当前下一个位置是 $s$ ，按照加入或不加入转移。
$f_{i+1,j+1,0/1}\gets f_{i,j,0/1}$
$f_{i+1,j,0}\gets f_{i,j,0/1}$
如果下一个是 $t$，按照 $s$ 的前缀，加入或不加入转移。
$f_{i+1,j-1,0/1}\gets f_{i,j,0/1}\times j$
$f_{i+1,j,1}\gets f_{i,j,1}$
答案即为 $f_{2N,0,0}+f_{2N,0,1}$
\end{frame}
\section{CF1792F1}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1792F1}{CF1792F1}}
给定一个有 $ n $ 个顶点的无向完全图。完全图是指任意两个顶点之间都有一条边相连。你需要将图中的每条边涂成红色或蓝色（每条边只能涂一种颜色）。
对于一个顶点集合 $ S $，如果对于 $ S $ 中的任意一对顶点 $ (v_1, v_2) $，都存在一条仅经过 $ S $ 中顶点且只经过红色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是红连通的。同理，如果对于 $ S $ 中的任意一对顶点 $ (v_1, v_2) $，都存在一条仅经过 $ S $ 中顶点且只经过蓝色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是蓝连通的。
你需要对图进行涂色，使得：至少存在一条红色边； 至少存在一条蓝色边；对于每一个满足 $ |S| \ge 2 $ 的顶点集合 $ S $，$ S $ 要么是红连通的，要么是蓝连通的，但不能同时两者都是。
请计算有多少种不同的涂色方案，并将答案对 $ 998244353 $ 取模后输出。
$3 \le n \le 5 \times 10^3 $
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1792F1}{CF1792F1}}
引理：一个图，如果不连通，补图一定连通。
证明是容易的，对连通块的情况考虑即可。
本题中，发现，红蓝两种边染色互为补图。符合条件的图一定有一种颜色不连通。不妨记 $f_n$ 表示大小为 $n$ 的不是蓝色连通的符合条件的图的数量。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/CF1792F1}{CF1792F1}}
考虑包含 $1$ 的大小为 $i$ 的极大蓝色连通块。显然这部分应当不是红色连通的，那么这 $i$ 个点连边就有 $f_i$ 种方案。
对于剩下的 $n-i$ 个点，我们并不关心这部分是红色连通还是蓝色连通，因此染色方案为 $2\times f_{n-i}$ 。
由极大蓝色连通块定义，知 $i$ 个点和剩下 $n-i$ 个点连的都是红边。
有 $f_n\gets \binom{n-1}{i-1}\times f_i\times f_{n-i}\times 2$
注意，当 $i=n-1$ 时，最后不能乘 $2$ 的系数。
总复杂度 $O(n^2)$ 。
\end{frame}
\section{P7529}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7529}{P7529}}
Bessie 在二维平面上有 $N$ 个最爱的不同的点，其中任意三点均不共线。对于每一个 $1\le i\le N$，第 $i$ 个点可以用两个整数 $x_i$ 和 $y_i$ 表示。
Bessie 按如下方式在这些点之间画一些线段：
1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots,p_N$ 。
2. 她在点 $p_1$ 和 $p_2$ 、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
3. 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j<i$，她从 $p_i$ 到 $p_j$ 画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。
Bessie 注意到对于每一个 $i$ ，她都画上了恰好三条新的线段。计算 Bessie 在第 $1$ 步可以选择的满足上述性质的排列的数量，结果对 $10^9+7$ 取模。
$3\le N \le 40$，$0\le x_i,y_i \le 10^4$
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7529}{P7529}}
我们很容易看出来，所有合法的情况里，都有一个最大的三角形包含了所有的点。
此外，整个大三角形内部会被分割为一个个三角形。
记 $w_{i,j,k}$ 表示 $i,j,k(i<j<k)$ 为最大三角形的顶点时，在最大三角形外的顶点的数量。
记 $dp_{i,j,k}$ 表示 $i,j,k(i<j<k)$ 为最大三角形的顶点时，处理完最大三角形外的点的方案数。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7529}{P7529}}
倒序转移，将所有三角形按 $w$ 从小到大排序，第一个三元组对应的 $dp_{x,y,z}=1$。
考虑转移，对于 $(i,j,k)$ ，考虑枚举在这个三角形内部的点 $l$ ，分成了三个三角形，下面以 $(i,j,l)$ 为例。有
$dp_{i,j,l}\gets dp_{i,j,k} \times P(w_{i,j,l}-1,w_{i,j,l}-w_{i,j,k}-1)$
其中 $P$ 是排列，因为一定最后选择 $k$ 点，表示从剩下的 $w_{i,j,l}-w_{i,j,k}-1$ 点中选位置。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7529}{P7529}}
对于所有的三角形，更新答案 $ans$ 。有
$ans\gets dp_{i,j,k}\times 6\times P(n-3,n-3-w_{i,j,k})$
表示以 $i,j,k$ 作为最初选择的 $p_1,p_2,p_3$ ，自身有 $6$ 种排列，又可以把剩下的三角形内的点选位置。
\end{frame}
\section{P7213}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7213}{P7213}}
初始有 $2\times N$ 个石柱，对于 $1\le k\le N$ 均有两个石柱高度为 $k$，同时记第 $i$ 个石柱的高度为 $h_i$。
接下来会发生 $N$ 次地震，每次地震会使一些石柱的高度 $-1$，其他石柱高度不变。石柱 $i$ 地震时高度不变，当且仅当 $h_i\ge 1$ 并且对于 $j>i$ 都要有 $h_i\not=h_j$
$N$ 次地震后，恰好只剩下了 $N$ 个石柱。
现在给定仅存的 $N$ 个石柱的位置 $A_1,A_2,\ldots,A_N$，求出最初 $2\times N$ 个石柱高度的修建方案数 $\bmod~10^9+7$ 的值。
$1\le N\le 600$，$1\le A_i\le 2\times N$，$A_i< A_{i+1}$。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7213}{P7213}}
重要性质就是：如果当前后面出现了 $1$ 到 $h$ 的柱子高度，当前高度 $\le h$ 的都会直接震没。将最大的 $h$ 称为高度阈值，将上述的柱子称为标准柱。
记 $f_{i,j}$ 表示 $i$ 到 $n$ 的柱子，高度阈值为 $j$ 的方案数。
以下区分高度相同的柱子。
标准柱自然只有 $j$ 个，而且是从 $2j$ 个可能里面选出来的。一个很麻烦的问题是，如果选了初始高度超过 $j$ 的，我们很难知道到底选了什么。
考虑贡献后置。
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7213}{P7213}}
若当前柱子 $i$ 最终会消失，记 $c_0$ 为已经消失的柱子数（不包括 $i$）。
有 $2j$ 种可能高度，标准柱用掉 $j$ 个，已经用掉 $c_0$ 个，当前所选高度有 $j-c_0$ 种。
$f_{i,j}\gets (j-c_0)\times f_{i+1,j}$
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7213}{P7213}}
若当前柱子 $i$ 最终保留。
1.若高度 $>j+1$，不考虑具体高度，$f_{i,j}\gets f_{i+1,j}$
2.若高度为 $j+1$ ，需要考虑新的高度阈值 $k$，枚举这个 $k$ ，记 $c_1$ 为已经保留的柱子数 （不包括 $i$）。先选定标准柱的位置，然后确定这些标准柱的初始高度，用 $g_{k-j-1}$ 表示，确定当前的柱子高度，因为有 $2k$ 种选法，标准柱用掉 $k-1$ 个，有 $j$ 个不能选，共 $k-j+1$ 种。
有 $f_{i,k}\gets \binom{c_1-j}{k-j-1}\times g_{k-j-1}\times (k-j+1)\times f_{i+1,j}$
\end{frame}
\begin{frame}
\frametitle{\href{https://www.luogu.com.cn/problem/P7213}{P7213}}
$g_j$ 的定义是高度阈值为 $j$ 的初始高度方案数。
转移时，枚举第一个柱子的最终高度 $(i+1)$，选定新的标准柱位置，然后确定两边的初始高度，确定第一个柱子的高度即可。分析和上面一样，一共 $2j$ 的，用掉 $j-1$ 的，有 $i$ 不能用。
$g_j\gets \binom{j-1}{j-i-1}\times g_i\times g_{j-i-1}\times (j-i+1)$
答案为 $\frac{f_{1,n}}{2^n}$，总复杂度 $O(n^3)$。
\end{frame}
\end{document}