概率与期望

· · 算法·理论

前言

体验可能更好？？

洛谷中没贴代码，可以去我博客看代码。尝试过在洛谷里贴代码，但写的时候太麻烦了，而且很卡顿，遂放弃。

因为本人数学不是很好，且本人比较弱，所以本文部分内容不保障正确性，不过我确实是推了很久，想了很久，以我的理解呈现出来的。

注意，本文主要分析期望 DP，概率 DP 的内容较少。

基础理论

一些定义

可以先大概了解，在后续需要用到相关定义的时候再翻回来看。

概率的性质

假设某对 X 和 Y 组合的概率为 P(X=X_i, Y=Y_j)，这里的关系是且。

1.边缘概率公式

P(X=X_i)=\sum_{j} P(X=X_i, Y=Y_j)

还是比较显然，可以感性理解为 Y 把所有可能取值的概率都计算了（且这些取值是互斥的），那不就是 X=X_i 的概率吗。

2.所有概率和为 1

\sum_{i} P(X=X_i)=1

比较显然吧。感性理解就好，我不知道咋解释了。

3.全概率公式

若事件组 B_1, B_2, \ldots, B_n 是样本空间 \Omega 的一个互斥完备事件组，则对于任意事件 A，有：

P(A) = \sum_{i=1}^n P(B_i) \times P(A | B_i)

本质是将一个复杂事件 A 的概率，分解为多个简单事件 B_i 条件下的概率加权和，权重为各简单事件的概率。

正确性也比较显然，因为互斥完备事件组，保证了事件 A 发生的所有可能情况都被考虑且不重复，从而能够将 A 的概率正确分解。

一般的概率 DP 都需要用到此公式计算。因为此公式把一个问题拆分成若干子问题，就是 DP 的思想。还是很重要的。

一些推广：

I.连续型随机变量情况：

对于连续型随机变量 X 和 Y，全概率公式推广为：

P(A) = \int_{-\infty}^{+\infty} P(X = x) \cdot P(A | X = x)

II.多层全概率，可以将事件 A 的概率分解为多个层次的条件概率乘积和：

P(A) = \sum_{i} \sum_{j} P(B_i) \cdot P(C_j | B_i) \cdot P(A | B_i \cap C_j)

4.贝叶斯公式

是全概率公式的逆用，用于在已知事件 A 发生的条件下，求事件 B_i 发生的概率：

P(B_i | A) = \frac{P(B_i) \cdot P(A | B_i)}{\sum_{j=1}^n P(B_j) \cdot P(A | B_j)} = \frac{P(B_i) \cdot P(A | B_i)}{P(A)}

其中，分母 P(A) 就是全概率公式计算出的结果。

（部分内容先不解释了，我也不会，鸽子了）

来点简单应用！

袋中取球问题：一个袋子中有 3 个红球和 2 个白球。从中随机取出一个球扔掉，再随机取出一个球。求第二次取出红球的概率。

设事件 B_1 为第一次取出红球的概率，事件 B_2 为第一次取出白球的概率，事件 A 为第二次取出红球的概率。

显然这两个事件构成了一个互斥完备事件组，然后就能用全概率公式了，也就是有：

\begin{aligned} P(A) &= P(B_1) \times P(A|B_1) + P(B_2) \times P(A|B_2) \\ &= \frac{3}{5} \times \frac{2}{4} + \frac{2}{5} \times \frac{3}{4} \\ &= \frac{3}{5} \\ \end{aligned}

其实没啥特别的应用，主要还是为之后的期望准备一些理论基础。

期望的性质

1.期望的定义式

E(X) = \sum_i X_i \times P(X = X_i)

就是每种情况出现的概率乘上这种情况的权值。

本质就是本质是考虑概率权重后的平均取值，也就是加权平均数。

比如猜硬币，正面赢 X_1=2 元（概率 0.5），反面赢 X_2=0 元（概率 0.5），求赢钱数 X 的期望。

\begin{aligned} E(X) &= X_1 \times P(X=X_1) + X_2 \times P(X=X_2) \\ &= 2 \times 0.5 + 0 \times 0.5 \\ &= 1 \end{aligned}

意思是长期猜下去，平均每次能赢 1 元。注意这是一个期望值，赢 1 元在实际是取不到的。

2.期望的线性性

线性指的是加法和数乘（数乘可以用矩阵理解，一个数乘矩阵的时候就是数乘）。

1.和式的期望等于和式中所有项的期望之和，即：

E(X + Y) = E(X) + E(Y) E(\sum_{i=1}^{n} X_i) = \sum_{i=1}^{n} E(X_i)

一种感性理解：设 X 是你数学成绩（期望 80 分），Y 是语文成绩（期望 90 分），那么数学语文总成绩 X+Y 的期望就是数学成绩的期望与语文成绩的期望之和 80+90=170 分。

证明如下：

假设 X 有 2 个取值 X_1，X_2，Y 有 2 个取值 Y_1，Y_2，所有组合的概率为 P(X=X_i, Y=Y_j)，这里的关系是且。

\begin{aligned} E(X+Y) &= \sum_{i}\sum_{j} (X_i+Y_j) \times P(X=X_i, Y=Y_j) \\ &= \sum_{i}\sum_{j} X_i \times P(X=X_i, Y=Y_j) + \sum_{i}\sum_{j} Y_j \times P(X=X_i, Y=Y_j) \\ &= \sum_{i} X_i \times \sum_{j} P(X=X_i, Y=Y_j)+\sum_{j} Y_j \times \sum_{i} P(X=X_i, Y=Y_j) \\ &= \sum_{i} X_i \times P(X=X_i) + \sum_{j} Y_j \times P(Y=Y_j) \\ &=E(X)+E(Y) \end{aligned}

对于 X，Y 有多个取值证明逻辑是一样的，所以就证完了。

2.常数无论作为加数还是乘数，都可以提到外面，即：

E(X + c) = E(X) + c E(aX + c) = aE(X) + c E(aX + bY) = aE(X) + bE(Y) E[\sum_{i=1}^{n} a_i X_i] = \sum_{i=1}^{n} a_i E(X_i) (a_i 为常数)

一种感性理解：若数学成绩 X 的期望是 80 分，此时乘以 a=1.2 倍后再加 5 分（c=5），则新成绩的期望是 1.2 \times 80 + 5 = 101 分。

证明如下：

\begin{aligned} E(aX+c) &= \sum_{i} (aX_i + c) \times P(X=X_i) \\ &= a \times \sum_{i} X_i \times P(X=X_i) + c \times \sum_{i} P(X=X_i) \\ &= aE(X) + c \\ \end{aligned}

3.变量之间相乘是非线性的。因此对于两个变量相乘，期望不可拆解（只有相互独立时等式成立）。即：

E(XY) \neq E(X)E(Y)

一种感性理解：因为变量之间会相互影响，所以直接拆开就错了，因为你无法把影响体现出来。举例子懒得举了，自行举例即可。

证明不会。

3.全期望公式

若事件组 B_1, B_2, \ldots, B_n 是样本空间 \Omega 的互斥完备事件组（或随机变量 Y 的所有可能取值），则对任意随机变量 X，其期望 E[X] 可通过“条件期望加权求和”计算：

E[X] = \sum_{i=1}^n P(B_i) \times E[X | B_i]

全期望公式的本质可以简洁地表示为：

E[X] = E[E[X | Y]]

即“X 的期望等于 X 在 Y 条件下的期望的期望”，所以全期望公式也被称为“期望的期望”。

其本质是「期望的线性性质」与「全概率公式的延伸」。期望 DP 往往是根据此公式把期望拆分成若干期望，所以还是很重要的。

严谨证明的话我不会，但是我会一些感性证明，这一点在后面的例题分析中可以体现。

4.期望与方差的关系

方差 Var(X) 与期望之间的关系：

Var(X) = E(X^2) - (E(X))^2

根据方差定义：偏离期望的平方的期望，直接推式子就好。这里的 E(X) 其实就是一个常量。

\begin{aligned} Var(X) &= E[(X-E(X))^2] \\ &= E[X^2 - 2XE(X) + (E(X))^2] \\ &= E(X^2) - E[2XE(X)] + (E(X))^2 \\ &= E(X^2) - 2E(X) \times E(X) + (E(X))^2\\ &= E(X^2) - 2(E(X))^2 + (E(X))^2 \\ &= E(X^2) - (E(X))^2\\ \end{aligned}

例题分析

有了前面的理论铺垫，终于可以进入今天的正题，期望 DP 了。主要还是分析期望 DP，因为比较难理解。

有一些常规的套路解决这类 DP，这里以例题逐步分析。

例 1 绿豆蛙的归宿

给定一个起点为 1 ，终点为 n 的有向无环图。到达每一个顶点时，如果有 K 条离开该点的道路，可以选择任意一条道路离开该点，并且走向每条路的概率为 \frac{1}{K} 。问从 1 出发走到 n 的路径期望总长度。保证从任意点出发最终一定能走到 n。

方法一：初态顺推

一种很容易想到的，比较人性的方法，但同时会麻烦一点。

首先，因为是个 DAG，直接拓扑排序加 DP 就行。

定义 f_u 为从 1 出发走到点 u 的路径期望总长度。

接下来考虑转移，令 G_u 表示经过一条边后到达 u 的点集，g_u 表示从 1 出发到点 u 的概率。

根据期望定义，不妨设 f_v=\sum_i P(x=x_i) \times x_i。

此时从 v 经过 w 的长度走到 u，那么可以得到：

\begin{aligned} f_u &= \sum_i P(x=x_i) \times \frac{1}{|G_u|} \times (x_i+w) \\ &= \frac{1}{|G_u|} \sum_i P(x=x_i) \times x_i + \frac{w}{|G_u|} \sum_i P(x=x_i) \\ &= \frac{1}{|G_u|} f_v + \frac{g_v}{|G_u|}w\\ \end{aligned}

因为 f 实际上就是期望，也就是根据期望和概率的各种性质推一推式子。

上述是考虑了转移一个点的情况，此时再到一般情况，可以得到转移式：

f_u=\sum\limits_{v\in G_u} \frac{1}{|G_u|}f_v + \frac{g_v}{|G_u|}w

然后对于 g 用全概率公式算就行。

你还会发现这个转移式，是完全符合全期望公式的。所以我们在一种特定背景下证明了全期望公式。

那么其实下次直接考虑套用全期望公式求转移式就行了，不用再重推导一遍。

在实现时，为了方便可以直接刷表法，都一样的。

方法二：终态逆推

比较反直觉，但是很方便，主流的期望 DP 方法。

如果我们考虑把状态定义逆着来，定义 f_u 为从 u 出发走到点 n 的路径期望总长度，也是可以做的。

这里推导过程和方法一是一样的。令 G_v 表示 v 经过一条边后可到的点的点集，g_u 表示从 u 出发到点 n 的概率。

可以得到转移式：

f_v=\sum\limits_{u\in G_v} \frac{1}{|G_v|}f_u + \frac{g_u}{|G_v|}w

但是仔细观察可以发现，对于每个 u 都满足 g_u=1，因为题目保证了从任意点出发最终一定能走到 n。

于是我们可以省去 g_u，省去了对于概率的处理，更加方便。

但是在方法一中，g_u 就不一定为 1 了。举个简单的例子，在样例中 g_2=0.5，原因就是从 1 出发后会到达多个中间点，而这些中间点不一定能到 u，于是 g_u 不一定为 1。

方法三：期望的线性性质

利用期望的线性性质，E(X + Y) = E(X) + E(Y)，所以另外一种求期望的方式是分别求出每一种代价产生的期望贡献，然后相加得到答案。

在本题中，路径期望总长度等于每条边产生的期望贡献之和。每条边产生的期望又等于经过这条边的概率乘这条边的代价。所以，只需要算出每条边的概率即可。

相当于直接把期望 DP 转化为了概率 DP。

这里边 (u,v,w) 的经过概率不好直接计算，但如果能算出点 u 的经过概率是 f_u ，那么边 (u,v,w) 的经过概率是 f_u \times \frac{1}{|G_u|} ，对答案的贡献是 w \times f_u \times \frac{1}{|G_u|} 。

算 f 就是相当于全概率公式算。实现的时候可以刷表，然后又因为是刷表，边刷的时候边考虑这条边对答案的贡献就好，非常方便。

方法四：期望的定义式

这题不太适合用此方法，不太好讲，具体见下面的例题。

例 2 CF518D Ilya and Escalator

有 n 个人排成一列，每秒中队伍最前面的人有 p 的概率走上电梯（一旦走上就不会下电梯），否则不动。问 T 秒后，在电梯上的人数的期望。

方法一：初态顺推

考虑直接 DP，定 f_{i,j} 表示一共有 i 个人，过了 j 秒电梯上的期望人数。

然后用全期望公式，考虑第 i 个人上不上电梯，可以得出转移：

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

就做完了，很简便。

我们思考一件事，为什么这题用初态顺推的方法，却不用额外记录一个概率呢？因为这里的概率 p 是题目中直接给出的，于是我们并不需要额外记录。

方法二：终态逆推

定 f_{i, j}：前 i 秒电梯外有 j 个人，i+1 到 t 秒电梯上的期望人数。

因为我们只是想对期望进行逆推，所以只有计算期望的状态是逆过来的，其余状态都可以正着定义。

如何考虑 i 上不上电梯，然后得出转移：

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

就做完了。

当然，不管是方法一还是方法二，状态定义成电梯上有多少人也是可行的。这里已经实践了，发现是可行的，不展开细说了。

我们思考一件事，为什么终态逆推的时候概率和一定为 1 呢？这个问题也困扰了我很久，现在给出一个感性理解。

得先明白初态，终态的详细定义到底是什么。

可以类比 DP 理解，初态就是 DP 初始化时的某一状态。终态就是 DP 最后取答案时的某一状态。

或者类比树理解，可以把转移的情况当成树，树上每一个点对应着期望，即状态；每条边对应着概率，即各种权值。

根就是初态，叶子结点就是终态，转移的方向就可以是从终态往起点推，也可以是起点往终态推，其实也对应着 DP 和记忆化搜索两种方向。

当然转移不一定能抽象成一棵树。有时候会是有向图，还有可能带环，会复杂一点，此时一般需要高斯消元。

一般而言初态唯一，而终态可能唯一，可能不唯一，形象的理解就是当成一颗树的时候，多个叶子节点即多个终态。

以下内容可以挂到树上理解：

全部终态的概率和为才 1，正推时，概率和并没有考虑到全部终态，所以不为 1。

但倒推时，终态最终一定能推回到初态，即所有终态都能回到所有初态，然后全部终态概率和为 1，于是所有初态的概率总和也为 1，但是因为只有一个初态，所以对于概率就是 1。

于是初态唯一，不管终态唯不唯一，都可以考虑终态逆推，如果要初态顺推，需要多记一个概率，当然如果题目已经给出就不必记录。

这件事确实很抽象，我花了不下 3 天来理解这件事，真的是需要刷多点题，再慢慢体悟。

方法三：期望的线性性质

并不适用，因为结束状态并不明确，不好拆分成若干状态的贡献。

方法四：期望的定义式

根据期望的定义式，E(X) = \sum_i X_i \times P(X = X_i)，相当于所有可能取值乘上其对应概率。然后直接算其可能的取值，和对应的概率就好。

这题中，E(t) 表示表示过了 t 秒后在电梯上的人数的期望，P(i) 表示表示过了 t 秒后在电梯上有 i 人的概率。

那么有：

E(t) = \sum_{i=1}^{n} i \times P(i)

对于 P(i)，可以用全概率公式计算，即拆分成上一秒的若干情况，这其实就是类似方法一中的 DP。

定 f_{i,j} 表示过了 j 秒时有 i 个人在电梯上的概率。有转移：

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

就做完了，比较无脑。

回过头来分析下上一题为何不适用此方法。很简单，直接枚举所有路径，复杂度不能接受。

练习

1.P1365 WJMZBMR打osu! / Easy

给定一个序列，一些位置未确定（o 与 x 的几率各占 50\% ）。对于一个 ox 序列，连续 x 长度的 o 会得到 x^2 的收益，求最终得到的序列的期望收益。

定 f_i 表示序列前 i 个位置的期望收益。然后从 i 往前找到第一个为 x 的位置 j，考虑 [j+1, i] 这样连续一段 o? 序列的期望收益，转移给 f_i 即可。

但是复杂度不接受。

当可以维护期望的变化量时，可以用到一个期望常用 trick：把状态拆成类似前缀和的形式，然后转化为算期望的变化量，具体的就是设 f_{st}，表示从当前状态 st 变成下一状态 st' 的期望。原理就是期望的线性性质。

回到此题，就是设 g_i，表示从序列第 i-1 位到序列第 i 位的期望长度变化量。最后做一遍前缀和就算完了，即设 f_i=\sum_{j=1}^{i} g_j。

所以我们需要记录 l_i 表示为以 i 结尾的 comb 的期望长度。然后分类讨论即可。

根据期望的线性性质，全期望公式可以得出：

  1. s_i=$ o，$g_i=(l_{i-1}+1)^2-l_{i-1}^{2}=2l_{i-1}+1$ ， $l_i=l_{i-1}+1
  2. s_i=$ x，$g_i=0$ ， $l_i=0
  3. s_i=$ ?，$g_i=\frac{2l_{i-1}+1}{2}$ ， $l_i=\frac{l_{i-1}+1}{2}+\frac{0}{2}

2.P1654 OSU!

给定一个序列，每个位置为 o 的几率为 p_i ，为 x 的几率为 1-p_i。对于一个 ox 序列，连续 x 长度的 o 会得到 x^3 的收益，求最终得到的序列的期望收益。

上题加强版，也是考虑计算变化量。此题变化量形如 (x+1)^3-x^3=3x^2+3x+1，于是只需要维护 l_i，表示以 i 结尾的 comb 的期望长度，l2_i，表示以 i 结尾的 comb 的期望长度的平方。

注意 E(X^2)\neq E^2(X) ，即 l_i^2 \neq l2_i，所以维护 l2_i 是必要的。

3.P6835 [Cnoi2020] 线形生物

给定一条链，链上存在若干条返祖边 u_i \rightarrow v_i (u_i \ge v_i)，求从 1 到 n 期望步数。

因为概率题目并没直接给出，如果初态顺推需要额外记录概率。所以我们直接考虑终态逆推。

定 f_i 表示从 i 走到 n 的期望步数。但有返祖边的存在，这很难转移。

发现终态唯一，仍然沿用上题的 trick，计算变化量。

重新定 f_i 表示 i 走到 i+1 的期望步数。因为转化成算变化量，那么正推倒推是无所谓的，但是有返祖边，于是考虑顺推去做。

然后考虑 f_i 的转移式，就是考虑这一次走返祖边还是走链上的边。

我们方便推导，令 E_{x\to y} 表示 x 到 y 的期望步数，du_x 表示 x 的返祖边的条数，E 表示 x 的返祖边的边集。

\begin{aligned} E_{x\to x+1} &= \frac{1}{du_x+1}\times1+\frac{1}{du_x+1}\sum_{(x,y)\in E} (E_{y\to x+1}+1) \\ &= \frac{1}{du_x+1}+\frac{1}{du_x+1}\sum_{(x,y)\in E}\sum\limits_{i=y}^{x}E_{i\to i+1}+\frac{1}{du_x+1}du_x\\ &= 1+\frac{1}{du_x+1}\sum_{(x,y)\in E}\sum\limits_{i=y}^{x}E_{i\to i+1}\\ \end{aligned}

然后根据期望的线性性质，可以对变化量求前缀和优化。记 sum_x=\sum\limits_{i=0}^x f_i。

\begin{aligned} E_{x\to x+1} &= 1+\frac{1}{du_x+1}\sum_{(x,y)\in E} sum_x-sum_{y-1} \\ E_{x\to x+1} &= 1+\frac{1}{du_x+1}\sum_{(x,y)\in E} sum_{x-1}-sum_{y-1}+\frac{du_x}{du_x+1} E_{x \to x+1} \\ \frac{1}{du_x+1} E_{x\to x+1} &= 1+\frac{1}{du_x+1}\sum_{(x,y)\in E} sum_{x-1}-sum_{y-1} \\ E_{x\to x+1} &= du_x+1 +\sum_{(x,y)\in E} sum_{x-1}-sum_{y-1} \end{aligned}

推导一下式子，发现左右都含未知量，那就移项处理，最后整理即可。

甚至没有一个除法，所以直接大力取模没问题。

4.P2473 [SCOI2008] 奖励关

共有 K 轮操作，一共有 n 种物品，每一轮随机出现每一种物品，概率是 \frac{1}{n} ，物品可选可不选，对于选每一种物品，必须要在前面的轮先选给定的部分物品，每一种物品的价格可正可负。求 K 轮后按最优方案选择的期望价格。

发现物品数量很少可以状压，然后需要知道当前轮数。基本 DP 状态就确定了。然后思考正推还是倒推。

就算到了第 K 轮选的物品具体选择也不唯一，也是多个终态。可以考虑倒序逆推。

定 f_{i, s} 表示，前 i 个物品选或不选构成集合 s，第 i+1 到第 K 轮的最优期望值。

也是和例题 2 同理，只需要考虑对期望进行逆着定义就好。

考虑转移，就是枚举当前随机出物品 k，然后考虑这个物品选不选。

但这题又有决策，又有期望，如何转移呢？对于有随机性的事情，算期望的需要累加。而对于可以自行决策的事情，我们算期望时可以取最值。

因为取最值就相当于最优决策，而随机事件我们无法决策，所以对于期望而言就是直接累加。

令 mask_k 表示选 k 这个物品必须先选 mask_k 这些物品，根据上面我们推出转移式：

\begin{cases}max(f_{i+1, s}, f_{i+1, s|(1<<k)}+val_k) & (s \& mask_k)=mask_k \\ f_{i+1, s} & \text{otherwise} \\ \end{cases}

这里的概率就是 \frac{1}{n}，因为是倒推所以概率和为 1。

我们思考下如果是正推呢？那就不一定是 \frac{1}{n} 了。

因为正推过程中，对于一个 i，其 s 可能是不合法的，但这个状态又算一个终态数，转移过程中必须得减去那些不合法的终态数，那概率就不为 1 了。

举个例子，正推可能会出现 \frac{1}{3} \times f_{1, 100}+\frac{1}{3} \times f_{1, 001}+\frac{1}{3} \times f_{1, 101}\to f_{2, 101} 的情况，这并不是一个合法的转移。而这样 \frac{1}{2} \times f_{1, 100}+\frac{1}{2} \times f_{1, 001} \to f_{2, 101} 才是一个合法的转移。也就是需要把不合法的终态数减去。但这个无法直接得到，需要额外记录，所以才会说正推过程中需要额外记录一个概率。

而倒推允许类似第一种转移的情况。所以概率和就是 1。这里在一种特定背景下解释了例题 2 中比较抽象的结论。

5.P1850 [NOIP 2016 提高组] 换教室

有 n 个班级，班级间有距离，你要依次到每个班级，你有最多 m 次换课机会让你从到班级 c_i 转换到 d_i，但每次换课只有 k_i\% 的概率能够成功，求班级 1 到班级 n 的距离总和的期望最小是多少？

首先这题图论部分和期望部分是独立的，可以先求个最短路，接着考虑期望 DP。

考虑你需要知道什么信息。显然需要记录到了哪个班级，用了几次换课机会。

还得记录你当前处于哪个班级中，这样你就能从上一个班级走过来。不过换到哪个班级是随机事件，无法直接记录，这样记录会很奇怪。但可以考虑记成在这个班级是否进行了换课操作。后续再考虑概率。

然后考虑正推还是逆推。发现题目把概率已经给你了，无需额外记录概率，直接考虑顺推。

考虑转移，就是一个大力分讨，考虑当前班级用不用换课操作，上一个班级用不用换课操作即可，以及讨论换课是否成功。 这题和上题一样，期望中带有操作。对于你可以决策的，取最值算概率，随机事件，相加算概率即可。 具体一些就是： 考虑第 $i$ 次不换课，即 $f_{i, j, 0}$： - 第 $i-1$ 次不换课，即 $f_{i-1,j,0}$，代价分为：$dis_{c_{i-1}, c_i}

综合两种情况，转移方程为：

f_{i,j,0} = \min\left( f_{i-1,j,0} + dis_{c_{i-1}, c_i},\ f_{i-1,j,1} + p_{i-1} \times dis_{d_{i-1}, c_i} + (1-p_{i-1}) \times dis_{c_{i-1}, c_i} \right)

考虑第 i 次换课，即 f_{i, j, 1}：

综合两种情况，转移方程为：

f_{i,j,1} = \min\bigg( &f_{i-1,j-1,0} + p_i \times dis_{c_{i-1}, d_i} + (1-p_i) \times dis_{c_{i-1}, c_i}, \\ &f_{i-1,j-1,1} + (1-p_i) \times p_{i-1} \times dis_{d_{i-1}, c_i} + p_i \times p_{i-1} \times dis_{d_{i-1}, d_i} \\ &\quad + p_i \times (1-p_{i-1}) \times dis_{c_{i-1}, d_i} + (1-p_i) \times (1-p_{i-1}) \times dis_{c_{i-1}, c_i} \bigg) \end{aligned}

6.Pku3156 Interconnect

给定无向图 G(V,E)，每次操作为等概率随机添加一条非自环边 (u,v)，求出使得 G 连通的期望操作次数。

|V| \le 30,|E| \le 1000

由于每次加边是等概率的，且每次加边要么不改变连通性，要么把两个连通块合并，就是说我们只关心图的连通状况。

注意到连通块大小和数量都很小，于是，用类似状压的技巧，暴力记录集合作为状态。

即状态记为每个连通块 C_i 的大小的集合。设有 k 个连通块，那么状态为 \{|C_1|,|C_2|,\cdots,|C_k|\} 。

记当前状态 S=\{|C_1|,|C_2|,\cdots,|C_k|\}，为避免重复，规定 |C_1|\le|C_2|\le\cdots\le|C_k|。

发现初态唯一，终态不唯一，直接倒序 DP。

设 g(S) 表示从当前状态开始到 G 连通的期望次数，显然图 G 连通就是 \{n\}，且有 g(\{n\})=0。

为了方便，我们记 T=\dbinom{n}{2}。

考虑转移，就是考虑每次随机从 T 种可能的边中选出一条边进行加边操作，我们分类讨论：

再根据期望的线性性质，就可以得到下面的转移式：

g(S) = 1 + \frac{P}{T} \cdot g(S) + \frac{Q}{T} \cdot g(S'_{i,j})

上面的式子包含 g(S) 自身，需要移项化简：

\begin{aligned} g(S) - \frac{P}{T} g(S) &= 1 + \frac{Q}{T} \cdot g(S'_{i,j}) \\ \frac{T-P}{T} g(S) &= 1 + \frac{Q}{T} \cdot g(S'_{i,j}) \\ g(S) &= \frac{T}{T-P} + \frac{Q}{T-P} \cdot g(S'_{i,j}) \\ \end{aligned}

然后就做完了。具体实现的时候可以考虑记忆化搜索，相当于先从初态递归下去到终态，这个过程就是不断合并的过程，然后再递归回来计算。

直接 DP 需要倒序进行，不过也行，相当于不断拆分，就是先枚举拆分哪个数，再枚举拆分成的值，是一样的。不过没有记忆化搜索直观。

然后可以用 map 映射一个 vector，非常牛的实现方法。

关于复杂度分析：

状态 S=\{|C_1|,|C_2|,\cdots,|C_k|\} 的数量等价于将 n 拆分成 k 个正整数之和的方案数 f(n,k)，其满足递推关系：

f(n,k)=\begin{cases}0, & n<k \\ 1, & k=1 \text{ or } n=k \\ f(n-1,k-1)+f(n-k,k), &\text{otherwise} \end{cases}

根据这个玩意算一下，会发现将 n 拆成若干个正整数之和的方案数为 p(n)=5604，复杂度就是 O(n^2p(n))。

7.Domination（ZOJ - 3822）

给定 n \times m 的网格，每天随机往没有糖果的地方放一个糖果，每一行每一列都至少有一个糖果的时候结束放糖果，求结束放糖果经过天数的期望值。

容易发现我们不关心每行每列到底是如何摆糖果，只关心有几行，几列放了糖果，以及当前是是第几天。

按照此状态，发现终态不唯一。考虑倒推，比较容易。

也可以考虑拆成变化量算，因为存在一种情况是：在某一天就已经让每一行每一列都至少有一个糖果了，那么应该在此打住，不应该继续往后推。所以考虑算变化量可以方便做到。

也可以考虑方法四，从期望的定义式出发，期望 DP 转化成概率 DP。这里详细讲讲此做法，其余的做法如果能理解前面的例题应该不算难事。

可以定 f_{i, a, b} 表示经过 i 天，有 a 行 b 列上至少有一个糖果的概率。答案就是：

\sum_{i=0}^{n\times m} i \times f_{i, n, m}

然后考虑刷表法会容易很多，因为在某一天就已经让每一行每一列都至少有一个糖果了，应该在此打住，不用当前概率往后更新。

考虑转移，就是考虑每天放糖果的操作，可能会多一行或多一列至少有一个糖果，这里分讨一下就好。具体如下：

f_{i+1,a,b} \leftarrow f_{i,a,b} \times \frac{a \times b-i}{n \times m-i} f_{i+1,a+1,b} \leftarrow f_{i,a,b} \times \frac{(n-a) \times b}{n \times m-i} f_{i+1,a,b+1} \leftarrow f_{i,a,b} \times \frac{a \times (m-b)}{n \times m-i} f_{i+1,a+1,b+1} \leftarrow f_{i,a,b} \times \frac{(n-a) \times (m-b)}{n \times m-i}

然后就做完了。

后记 & 总结

先放这么多例题吧。之后遇到好题再补。感觉已经能入门了，嘿嘿。

可能这只算是期望的冰山一角吧。其实还有很多套路没讲到，例如如果有后效性，需要高斯消元等技巧，贴个例题：P3232 [HNOI2013] 游走。不过我还没学高斯消元啥的，就先鸽子了。

稍微总结下，期望 DP 主要分 4 种方法。

  1. 正序顺推，在某些时候需要多记录一个概率，才能转移，比较麻烦，但胜在状态比较自然，不过不太推荐用，除非题目把概率已经给你了。

  2. 倒序逆推，把跟期望有关的那一个状态逆过来定义，可以少记录一个概率，更方便，更推荐此方法，且通常的期望 DP 都用倒推解决。

  3. 期望的线性性质，可以相当于以贡献的角度思考问题，也可以利用此性质计算变化量，把状态拆成类似前缀和的形式。

  4. 期望的定义式，直接枚举一些量，然后用定义式计算，胜在无脑，不过复杂度需要考虑下。可以把期望 DP 转换成概率 DP 处理。

好了好了。终于写完了。终于可以好好玩原神了。

参考文献

本文很大一部分内容参考了网上各种资料，这里贴出链接：

https://www.cnblogs.com/jjjxs/p/18703208

https://www.zhihu.com/question/464263211

https://www.cnblogs.com/RioTian/p/15053904.html

https://www.cnblogs.com/shiranui/p/16858780.html#41-%E7%BB%BF%E8%B1%86%E8%9B%99%E7%9A%84%E5%BD%92%E5%AE%BF

https://www.cnblogs.com/toorean/articles/18597974

https://www.cnblogs.com/4BboIkm7h/articles/19164055

https://www.cnblogs.com/Cat-litter/articles/18378615

https://www.cnblogs.com/RioTian/p/14117154.html

以及洛谷上的各种题解。这里不一一列出。