概率 dp
题单介绍
# 概率期望 DP
## ChapterI. 概率论入门
#### 定义
* $\Omega$: 样本空间，即所有基本事件的集合。
* $\mathcal{F}$: 事件集合，是由 $\Omega$ 的一部分子集组成的集合。需要满足以下性质：
1. $\Phi\in \mathcal{F}$。
2. $\forall _{E\in\mathcal{F}},\overline{E}\in\mathcal{F}$。
3. $\forall_{E_1,E_2\dots E_k\in\mathcal{F}},\cup_{i=1}^kE_i\in\mathcal{F}$。
* $\mathcal{P}$: 概率函数，是 $\mathcal{F}$ 到 $\R$ 的一个映射。需要满足以下性质：
1. $P(E)\in[0, 1]$。
2. $P(\Omega)=1$。
3. 若 $E_1,E_2\dots E_k$ 互斥，则 $P(\cup_{i=1}^kE_i)=\sum_{i=1}^kP(E_i)$。
为什么要有一个 $\mathcal{F}$ 而不直接把 $\mathcal{P}$ 定义为 $\Omega$ 到 $\R$ 的映射呢？因为对于样本数量为无穷大的时候我们无法定义单个基本事件的概率，例如一个取值在 $[0,1]$ 的随机变量等于 $0.5$ 的概率和在 $[0.3,0.6]$ 之间的概率我们无法准确的建立关联。所以我们需要一个 $\mathcal{F}$ 来避免这个问题。
#### 概率
* 加法公式：对于任意事件 $A,B$，有 $P(A+B)=P(A) + P(B) - P(AB)$。
* 减法公式：对于任意事件 $A,B$，有 $P(A-B)=P(A)-P(AB)$。
* 对立事件：对于任意事件 $A$，有 $P(A)+P(\overline A) = 1$。
* 条件概率：对于任意事件 $A,B$，有 $P(A|B)=\frac{P(AB)}{P(B)}$。
* 全概率公式：对于任意事件 $A$ 和满足 $\cup_{i=1}^k B_i=\Omega$ 且互斥一系列事件 $B_1,B_2,B_3\dots B_k$ ，有：
$P(A)=\sum_{i=1}^kP(AB_i)=\sum_{i=1}^kP(A|B_i)P(B_i)$。
**例一**
甲乙两工厂产品的次品率分别为 $1\%,2\%$，现有一批产品，其中甲乙工厂生产的各占 $60\%,40\%$，随机抽取一件。
(1) 这件产品是次品的概率。
(2) 该次品来此甲工厂的概率。
**Sol**
(1) 记 $A$ 表示是次品，$B_1$ 表示是甲工厂生产的，$B_2$ 表示是乙工厂生产的。
$\begin{aligned}P(A)&=P(AB_1)+P(AB_2)\\&=P(A|B_1)P(B_1)+P(A|B_2)P(B_2)\\&=0.01\times0.6+0.02\times0.4=0.014\end{aligned}$
(2)
$P(B_1|A)=\frac{P(AB_1)}{P(A)}=\frac{P(A|B_1)P(B_1)}{P(A)}=\frac{0.01\times0.6}{0.014}=\frac37$
#### 期望
取值为 $x_1,x_2\dots x_k$ 的离散随机变量的期望计算公式： $E(X)=\sum_{i=1}^k x_iP(X=x_i)$。
取值在 $[l,r]$ 中的连续随机变量的期望计算公式：$E(X)=\int_l^rf(x) \text{d}x$，其中 $f(x)$ 为 $X$ 的概率密度函数，满足 $P(l_0<x<r_0)=\int_{l_0}^{r_0}f(x)\text{d}x$。
#### 期望性质
线性性：
* $X,Y$ 为任意事件，则 $E(X+Y)=E(X)+E(Y)$。
* 若 $X,Y$ 独立，则 $E(XY)=E(X)E(Y)$。
* $E(kX)=kE(X)$。
## ChapterII. 经典例题
#### 常规
**例二 P1850 [NOIP 2016 提高组] 换教室**
有一张 $n$ 个点，$m$ 条带权边的无向图。
有一个人，总共有 $T$ 个时刻，他必须在第 $i$ 个时刻前往 $c_i$ 这个点，花费代价为从上一时刻所在点到这一点的最短路。
但是他可以选择最多 $S$ 个时刻，把 $c_i$ 改为 $d_i$，但是成功率只有 $k_i$（每个改动是否成功相互独立），且需要一次性决定好哪些时刻要改。
问最小代价的期望。
$n\le300,m\le90000,T\le2000,S\le2000$。
**Sol**
首先可以 Floyd 处理出任意两点最短路方便后续求代价。
设 $f(i,j,0/1)$ 表示考虑到第 $i$ 节课，前面已经要换 $j$ 节课了，当前这节课换不换的最小代价的期望。
根据期望定义有：
$$
f(i,j,0)=\min(f(i-1,j,0)+w_{00}(i-1,i),f(i-1,j,1)+w_{10}(i-1,i))
\\
f(i,j,1)=\min(f(i-1,j-1,0)+w_{01}(i-1,i),f(i-1,j-1,1)+w_{11}(i-1,i))
$$
其中：
$$
\begin{aligned}
&w_{00}(i,j)=dist(c_i,c_j)
\\
&w_{10}(i,j)=(1-k_i)dist(c_i,c_j)+k_idist(d_i,c_j)
\\
&w_{01}(i,j)=(1-k_j)dist(c_i,c_j)+k_jdist(c_i,d_j)
\\
&w_{11}(i,j)=(1-k_i)(1-k_j)dist(c_i,c_j)+(1-k_i)k_jdist(c_i,d_j)+k_i(1-k_j)dist(d_i,c_j)+k_ik_jdist(d_i,d_j)
\end{aligned}
$$
复杂度 $O(n^3+ST)$。
**例三 P2473 [SCOI2008] 奖励关**
你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。
宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说，即使前 $(k-1)$ 次系统都抛出宝物 $1$（这种情况是有可能出现的，尽管概率非常小），第 $k$ 次抛出各个宝物的概率依然均为 $\frac 1 n $。
获取第 $i$ 种宝物将得到 $p_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $s_i$。只有当 $s_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，$p_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。
假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？
$1 \leq k \leq 100$，$1 \leq n \leq 15$，$-10^6 \leq p_i \leq 10^6$。
**Sol**
注意到 $n$ 是非常小的，而且你要得知一个物品能不能选必然得知道哪些物品选过，所以自然而然的考虑状压dp。
设 $f(i,S)$ 表示系统抛出 $i$ 次宝物后，获取过的宝物集合为 $S$ 时能获得的最大价值的期望。
考虑一次抛出，根据期望定义就有：
$$
f(i,S)=\frac{\sum\limits_{j\in S}\max(f(i-1,S),f(i-1,S)+p_j,f(i-1,S-\{j\})+p_j)+\sum\limits_{j\not\in S}f(i-1,S)}{n}
$$
复杂度 $O(nk2^n)$，可以接受。
~~这也不是很难啊，为啥评紫。~~
#### 后效性
**例四 青蛙跳荷叶**
有一只青蛙，有 $n$ 片荷叶排成一排，依次编号为 1~$n$。
青蛙初始在 $n$ 号荷叶上，每次他会等概率跳到当前所在荷叶到 $1$ 号荷叶之中任意一片。
问这只青蛙期望跳多少次跳到 $1$ 号荷叶？
$n\leq10^6$。
**Sol**
设 $f(i)$ 表示当前在 $i$ 号荷叶时，期望还需要跳的次数。
考虑期望的定义有。
$$
f(i)=\frac{\sum\limits_{j=1}^if(j)}{i}+1
$$
注意等式两边都有 $f(i)$，也就是有后效性，显然不能直接递推，但是我们把右边的 $f(i)$ 挪到左边就好了：
$$
(i-1)f(i)-i=\sum_{j=1}^{i-1}f(j)
$$
这样就可以递推了，不过是 $O(n^2)$ 的。注意到右边那一块实际上是 $f(i)$ 的前缀和，因此记上前缀和就是 $O(n)$ 了。
**例五 P3232 [HNOI2013] 游走**
给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。
小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。
$2\leq n \leq 500$， $1 \leq m \leq 125000$，$1 \leq u, v \leq n$，给出的图无重边和自环，且从 $1$ 出发可以到达所有的节点。
**Sol**
考虑设 $f_{u,v}$ 表示 $(u,v)$ 这条边期望经过次数，会发现方程很难写。
考虑换一个状态，设 $f(u)$ 表示 $u$ 点经过的期望次数。
那么就有：
$$
f(u)=\frac{\sum\limits_{(u,v)\in E\and v\neq n} f(v)}{deg_u-[(u,n)\in E]}+[u==1]
$$
注意到这个方程的后效性无法简单的消除，但我们可以将其处理成 $n$ 元一次方程组的形式，便可以通过高斯消元求出每个 $f(u)$。
求出 $f(u)$ 之后，一条边 $(u,v)$ 的期望经过次数就可以表示为 $\frac {f(u)}{deg_u}+\frac{f(v)}{deg_v}$。
然后按照每条边的期望经过次数排序后贪心分配编号即可。
$$
g(i,u) = \sum_{(u,v)\in E} \frac{g(i - 1,v)}{\text{deg}_v}
\\
\begin{aligned}
f(u)&=\sum_{i=0}^{+\infty}g(i,u)
\\
&=\sum_{i=0}^{+\infty}\sum_{(u,v)\in E} \frac{g(i - 1,v)}{\text{deg}_v}
\\
&=\sum_{(u,v)\in E} \frac{\sum_{i=0}^{+\infty}g(i,v)}{\text{deg}_v}
\\
&=\sum_{(u,v)\in E}\frac{f(v)}{deg_v}+[u==1]
\end{aligned}
$$
**例六 CF24D Broken robot**
$n$ 行 $m$ 列的矩阵，现在在 $(x,y)$，每次等概率向左，右，下走或原地不动，但不能走出去，问走到最后一行期望的步数。
注意，$(1,1)$ 是木板的左上角，$(n,m)$ 是木板的右下角。
$1\le n,m\le 10^3$，$1\le x\le n$，$1\le y\le m$。
**Sol**
设 $f(i,j)$ 表示从 $(i,j)$ 走到第 $n$ 行的期望步数，那么有（不考虑 $m=1$ 的平凡情况）：
$$
f(i,j)=\begin{cases}\frac{f(i,j+1)+f(i-1,j)}2 &j=1\\\frac{f(i,j+1)+f(i,j-1)+f(i-1,j)}3&1<j<m\\\frac{f(i,j-1)+f(i-1,j)}2&j=m\end{cases}
$$
这是有后效性的。直接高消 $n^6$ 显然不能接受。
注意到每层之间是无后效性的，所以可以每一层拿出来做了高消再做下一层，但是 $n^4$ 也无法接受。
注意到系数矩阵实际上非常稀疏，将其画出来发现每行只有连续的两三个数，因此我们可以通过稀疏矩阵高消线性的求出一行，最终总复杂度为 $O(n^2)$。
## ChapterIII. 神秘题
**例七 HDU4336 Card Collector**
有一个游戏，有 $n$ 个角色，每次抽卡有 $p_i$ 的概率抽出第 $i$ 个角色（包括已经抽出来了的）。
问期望抽多少次才能把所有角色都抽出来。
$n\le20$。
**Sol1**
直接状压设 $f(S)$ 表示已经抽出了 $S$ 还要期望抽多少次。
那么就有：
$$
f(S)=\sum\limits_{i\in S}f(S)p_i+\sum\limits_{i\not\in S}f(S+\{i\})p_i+1
$$
有后效性，移个项就好了。
复杂度 $O(n2^n)$。
**Sol2**
设 $t_i$ 表示每个角色第一次被抽出来的抽数，那么要求的就是 $E(\max t_i)$。
设 $T=\{1,2\dots n\}$，根据 $\min/\max$ 容斥和期望的线性性我们有：
$$
\begin{aligned}
E(\max_{i\in T} t_i)&=E(\sum_{S\subset T}(-1)^{|S|-1}\min_{i\in S}t_i)
\\
&=\sum_{S\subset T}(-1)^{|S|-1}E(\min_{i\in S}t_i)
\end{aligned}
$$
$E(\min_{i\in S} t_i)$ 意思是 $T$ 这个集合中第一个被抽出来的角色的抽数的期望。那么我们从头一开始每一抽要么在集合内，要么在集合外，一旦抽到集合内就结束了，可以得出 $E(\min_{i\in S}t_i)=\frac{\sum_{i\in T}p_i}{\sum_{i\in S}p_i}$。
那我们只需要快速求出每个集合内角色的 $p_i$ 之和就能算答案了。
简单递推就可以做到 $O(2^n)$。
**例八 P6375 「StOI-1」小Z的旅行**
一块空地，有$n$座山，每座山有一个高度值$h$。小Z在最高的山上，要去最低的山。
他有如下移动方案：
$1.$ 移动到一座比当前山低的山；
$2.$ 移动到和当前山一样高的山（不可停留在当前山），对于每一高度只能执行一次该方案（即不可以连续 $3$ 次或以上到达同一高度的山）。
每次移动都会耗费体力值，耗费的体力值为两座山的水平距离（若从第 $i$ 座山移动到第 $j$ 座山，则耗费 |$i-j$| 点体力值）。
小Z**每次**若有多种方案移动，则会**等概率**选择任意一种，求耗费体力值的期望对 $998,244,353$ 取余后的结果。
$1 ≤ n ≤ 500000$，$1 ≤ h ≤ 10^{9}$。
**Sol**
没啥特别的，高度离散化之后从小到大看，每段高度相同的山一起处理。
设 $f(i,0/1)$，表示当前在第 $i$ 座山上，是否是第一次到这个高度的山，走到最低高度的山的期望步数。
记 $cnt_i$ 表示高度小于等于 $i$ 的山的个数。
$$
f(i,0)=\frac{\sum\limits_{h_j<h_i}(|i-j|+f(j,0))+\sum\limits_{h_j=h_i\and i\neq j}(|i-j|+f(j,1))}{cnt_{h_i}-1}
\\
f(i,1)=\frac{\sum\limits_{h_j<h_i}(|i-j|+f(j,0))}{cnt_{h_i-1}}
$$
贡献里 $|i-j|$ 可以强行拆开，然后就需要一个二维数点的操作，维护一个树状数组即可。
复杂度 $O(n\log n)$。
**例九 P5298 [PKUWC2018] Minimax**
有一棵树，给出每个叶节点的点权（互不相同），非叶节点 $x$ 有两个子节点，且其点权有 $p_x$ 的概率是子节点点权较大值，有 $1-p_x$ 的概率是子节点点权较小值。假设根节点 1 号节点的点权有 $m$ 种可能性，其中权值第 $i$ 小的可能点权是 $V_i$，可能性为 $D_i$，求 $\sum_{i=1}^m{iD_i^2V_i}$。
$n\leq3\times10^5$。
**Sol**
设 $f(u,i)$ 表示 $u$ 点取值为 $i$ 的概率。
记 $lc,rc$ 分别为左右儿子，那么有：
$$
f(u,i)=p_u(f(lc,i)\sum_{j<i}f(rc,j)+f(rc,i)\sum_{j<i}f(lc,j))+(1-p_u)(f(lc,i)\sum_{j>i}f(rc,j)+f(rc,i)\sum_{j>i}f(lc,j))
$$
直接 dp 是 $O(n^2)$ 的，显然不能接受。
注意到如果我们使用启发式合并来维护状态，可以将有效状态数降到 $O(n\log n)$。
考虑启发式合并时转移，转移操作相当于若干次区间乘和区间求和，可以用文艺平衡树维护。
总复杂度 $O(n\log^2n)$。
但是实际上进一步我们还可以用线段树合并来替换文艺平衡树启发式合并，实现略微复杂，可以做到 $O(n\log n)$。
## ChapterIV.练习题
**P9428 [蓝桥杯 2023 国 B] 逃跑**
**P8580 [CoE R5] 罚球**
**P5011 水の造题**
**P4284 [SHOI2014] 概率充电器**
**P4707 重返现世**