概率 DP 杂题总结 | Arahc's Home

前言

常规的概率 DP 题型有：

等概率随机排列相关。
按某种规则等概率构造树或图相关。
每一步按某种概率进行决策相关。
运用 DS 或全概率公式等操作巧妙优化。
Min-max 容斥。

上述题型基本都可以一眼得出算法方向是概率 DP。不常见的概率 DP 相关，这里不作太多解释，但是可以上个小 Trick：

求所有情况对应的答案和之类。
根据概率和期望的特性直接推结论（请注意，期望的线性性不要求事件相互独立）。
因概率 DP 的转移方程简单而可以展开成通式。

当然，这三种题都还可能属于计数 DP 或思维题。

例题

CF518D Ilya and Escalator

有 $n$ 个人，每秒钟最前面的人有 $p$ 的概率离开，否则概率不动。求 $t$ 秒期望离开人数。

$n,t\leq 2\times10^3$ 。

题解

因为数据范围允许 $nt$ 乱搞，不妨就把题目的关键信息“人数”和“时间”当做状态。设 $f_{i,j}$ 表示考虑到了第 $i$ 个人，时间为第 $j$ 秒的期望人数。有两种情况：

这个人在这一秒离开，由 $f_{i-1,j-1}$ 转移，概率为 $p$ 。
这个人不离开，由 $f_{i,j-1}$ 转移，概率为 $1-p$ 。

因此：

f_{i,j} = p(f_{i-1,j-1}+1) + (1-p)f_{i,j-1}

CF280C Game on Tree

给定一个树，每次操作随机选一个点并删除它的子树。求把树删空的期望次数。

$n\leq 10^5$ 。

题解

用期望的线性性，考虑每个点被删的期望次数。若这个点没有被删除，当且仅当它和它的所有祖先没有被删除。如果某次操作这个点删掉了，那么这个点刚好被选中并删除的概率，就是所有可能导致这个点删掉的点的个数的倒数，即 $\frac{1}{dep_i}$ 。

因此答案为所有点深度的倒数和。

CF908D New Year and Arbitrary Arrangement

一个空字符串。每次有 $p$ 的概率在末尾加一个 $\tt{a}$ ，否则加一个 $\tt{b}$ 。当出现 $k$ 个子序列 $\tt{ab}$ 时结束。求 $\tt{ab}$ 子串数的期望。

$k\leq10^3$ 。

题解

用 $f_{i,j}$ 表示有 $i$ 个 a， $j$ 个子序列的串数的期望。则：

f_{i+1,j} \gets f_{i+1,j} + pf_{i,j}

f_{i,i+j} \gets f_{i,i+j} + (1-p)f_{i,j}

第一维的大小是无穷大，无法实现。考虑从 $i=k$ 时开始推边界条件：

E(x) = \sum p^i(1-p)(k+i) = k+(1-p)\sum ip^i

后面这个是等比数列求和的变形，可以得到：

E(x) = k -1 + \frac{1}{1-p}

解决边界条件后，配合前面的转移方程 $k^2$ 完成。

Luogu4284 概率充电器

给定一个树，每条边有 $p_i$ 的概率导电，每个点有 $q_i$ 的概率自身带点。求期望有多少个点有电。

$n\leq 5\times 10^5$ 。

题解

期望有多少个点通电，等价于求所有点通电的概率之和。一个点有电分为三种情况：

子树内（包括这个点本身）有点把电传过来。
子树外有点把电传过来。

子树内的可以常规树形 DP 做。 $f_u\gets (1-f_u)f_vp_i$ ，即当前点没有电，然后通过 $v$ 传递过来。

如果考虑子树外，也就是第一次 DP 完后再进行第二次 DP，就会发现 $u$ 会对 $v$ 造成影响，而 $v$ 影响的一部分其实是第一次 DP 中 $v$ 给 $u$ 的。

这里用到了这个题最精妙的思想：如何把算重的贡献给去掉，也就是我们需要这个儿子对父亲做贡献前的状态。把DP 方程具体化，区分 $f_{u,now},f_{u,last}$ ：

f_{u,now} = f_{u,last} + (1-f_{u,last})f_vp_i

因此：

f_{u,last} = \frac{f_{u,now}-f_vp_i}{1-f_vp_i}

所以我们可以还原出更新前的 $f_u$ ，就可以用第一次 DP 的方程做了： $f_v\gets (1-f_v)f_{u,last}p_i$ 。

Luogu3600 随机数生成器

有一个序列 $a$ ， $a_i$ 在 $[1,x]$ 中随机。多次询问查询 $[l,r]$ 的最小值。求所有查询结果的最大值的期望。

$n,x,q\leq 2000$ 。

题解

显然被另一个区间完全包含的区间是无意义的。因此你可以认为所有区间没有包含关系。考虑全概率公式：

E(x) = \sum_{i\geq 0} P(x\geq i)

因为这里单次询问算的是最小值，所以转化为求 $1-P(x<i)$ 。也就是说所有区间内都至少有一个数小于等于 $i-1$ 。

因为没有包含关系，所以按左端点排序后，右端点也有序。排序后，显然，一个符合条件的数只能对一组编号连续的区间产生贡献，问题转化为：有一些点，这些点能对一段编号连续的区间产生贡献，产生贡献的概率为 $\frac{i-1}{x}$ ，求所有区间都有点给它产生贡献的概率。

这无疑就是颠倒了点和区间，所以问题转化为：给定一些区间，一个区间能覆盖区间内点的概率为 $\frac{i-1}{x}$ ，求所有点都能被覆盖的概率。设 $f_i$ 表示选择这个区间，且本区间能覆盖到的右端点以前的所有点都被覆盖的概率，则枚举上一次选的区间 $j$ ，满足 $r_j\geq l_i-1$ 才能满足这之前的点都被覆盖，所以有：

f_i\gets \frac{i-1}{x}\left[ \sum_{r_j\geq l_i-1} f_j\left(1-\frac{i-1}{x}\right)^{i-j-1} \right]

答案为：

\sum_{r_i=m} f_i(1-\frac{i-1}{x})^{n-i}

双指针优化可以做到 $\mathcal O(n)$ 。

Luogu5298 Minimax

一个二叉树，叶子有互不相同的点权，其他点有 $p_i$ 的概率权值为左右儿子权值的 $\max$ ， $(1-p_i)$ 的概率为 $\min$ 。

设根权有 $m$ 种可能，从小到大依次为 $d_i$ ，可能性为 $p_i$ 。求 $\sum_{i=1}^m id_ip_i^2$ 。

$n\leq 3\times 10^5$ 。

题解

如果我们按照最终答案设计状态，这题会非常难办。因为两个子树的权值合并改变了每个可能的结果的排序，因此会很复杂。按照前面的套路，应该以概率来设计状态。

设 $f_{i,j}$ 表示 $i$ 节点权值为 $j$ 的概率。 $l,r$ 为左右儿子。一个节点取到这个值，可能是因为左儿子取到这个值，且右儿子取到的值没有传递上取，或镜像同理。单独考虑左儿子的情况，右儿子无法传上它的值一定为：

这个点随机到取最大值，而右儿子的值比 $j$ 小。
这个点随机到取最小值，而右儿子的值比 $j$ 大。

右儿子传上来的情况同理，因此设计转移：

A = f_{l,j} \left[ p_i\sum_{k=1}^{j-1} f_{r,k} + (1-p_i) \sum_{k=j+1}^m f_{r,k} \right]

B = f_{r,j} \left[ p_i\sum_{k=1}^{j-1} f_{l,k} + (1-p_i) \sum_{k=j+1}^m f_{l,k} \right]

f_{i,j} \gets A+B

前缀和优化为 $n^2$ 后还是过不去。考虑线段树可以维护前后缀和以及区间查询。因此从下往上线段树合并求出 $f$ 即可。

Luogu5472 斗主地

一套牌，第 $i$ 张为 $i$ 或 $i^2$ 。进行 $m$ 次洗牌，问洗牌后每个位置的牌期望。一次洗牌定义如下：

给定参数 $A$ ，从上往下取前 $A$ 张分成两堆。建立初始为空的第三堆牌，设两堆分别有 $X,Y$ 张，则有 $\frac{X}{X+Y}$ 的概率取出第一堆的最底下的牌，否则取出第二堆牌的最底下一张，然后放到第三堆牌的顶端，如此反复直至 $X=Y=0$ 。

$n\leq 10^7,m\leq 5\times10^5$ 。

题解

$n$ 很大，而且每一个位置的权值期望都要求，非常不方便直接 DP。考虑到最开始的权值要么是 $i$ 要么是 $i^2$ ，猜测结论：权值与编号为一次函数时，洗牌后期望还是一次函数关系，二次函数同理。

再根据期望具有可加性，显然把第一次洗牌后的期望作为权值，算第二次洗牌得到的期望，结果和连续两次洗牌后的期望应该是一样的。这也是期望的小 Trick。

也就是说如果结论正确，就可以把求 $n$ 个位置的期望的问题，转化为求三个位置洗 $m$ 次牌后期望的问题，然后用拉格朗日插值（当然也可以直接待定系数）求出编号和洗 $m$ 次牌后的期望的关系。

那就相当于求常数个数的位置的期望。问题转化为：给定一个位置 $p$ ，求原牌洗牌 $m$ 次后，第 $p$ 个位置的牌的权值的期望。再根据前面的结论，连续洗牌两次，可以相当于洗第一次牌后，把权值当成第一次洗牌的期望，再洗第二次牌。加上这个性质就可以概率 DP 做了。然后任取三个 $p$ 跑 DP，用拉插求其他的 $p$ 的答案即可。

关于结论为什么正确，因为主要涉及数学内容且较复杂，这里没有展开，可以参考这篇博客的证明。

upd：貌似不需要跑 DP，直接把 $p=1,2,n$ 三个值代入可以推通式简单求解。