解决期望问题使用定义法, 或者 DP 倒推的方式，当前为初始状态，距离目标还需要的步数为期望。

基本模型

逆推方式

$f_i$ 表示当前状态到达目标状态的期望，按照期望线性的定义，得到：

$$f_i=\sum{p_{i,j} \times (f_j+cost(i,j))}$$

其中 $j$ 是状态 $i$ 下一个阶段状态。

特殊地，当 $cost$ 为定值 $c$

$$f_i=\sum p_{i,j} \times f_j+c\times\sum{p_{i,j}}=\sum p_{i,j} \times f_j+c$$

顺推

$f_i$ 从起点走到状态 $i$ 的期望

$$f_i=\sum{p_{j,i}*(f_j+cost(j,i))}$$

其中 $j$ 是 $i$ 上一个阶段状态。

特殊情况，对于很多线性问题，上一个阶段 $j=i-1$ , 即从 $i-1$ 转移到 $i$ ，可以得到

$f_i=f_{i-1}+ \sum{p_{i-1,i}*cost(i-1,i)}$

经典问题

涂格子1

• $n$ 个格子，每次随机涂一个，求涂 $m$ 次后期望涂色格子数期望。

  $f_i$ 表示涂完 $i$ 次后期望涂色格子数量。

  $f_i=f_{i-1}+\frac{f_{i-1}}{n}*0+\frac{n-f_{i-1}}{n}*1=(1-\frac{1}{n})*f_{i-1}+1$

涂格子2

• $n$ 个格子，每次随机涂一个，求涂满 $m$ 个格子的期望次数。

  $f_i$ 表示当前涂了 $i$ 个格子，到涂满 $m$ 个格子期望次数

  $f_i=(f_{i+1}+1)*\frac{n-i}{n}+(f_i+1)*\frac{i}{n}$

  $f_i=f_{i+1}*\frac{n-i}{n}+f_i*\frac{i}{n}+1$

  得到 $f_i=\frac{\frac{n-i}{n}*f_{i+1}+1}{1-\frac{i}{n}}$

  $f_m=0,ans=f_0$

涂格子3

• 有 $n(n \le 20)$ 个格子，每次会涂一个格子，其中涂第 $i$ 个格子的概率是 $p_i(\sum{p_i}=1）$ , 求每个格子都被涂色的期望次数。

  因为涂到每个格子的概率不同，所以没法把“格子数量”当成一维状态，只能使用状压。

  设 $f_s$ 表示涂格子的状态为 $s$ 时到涂满还需要的次数。

  $f_s=\sum_{i=0}^{n-1}{ p_i*f_{s|2^i}} + 1$

  $f_{2^n-1}=0$

---

例. P4316 绿豆蛙的归宿

【题意简化】

给定 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$ ，终点为 $n$ ，第 $i$ 条边的长度为 $l_i$. 从起点出发能够到达所有的点，所有的点也都能到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果该结点有 $k$ 边出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$.

• DAG 上求期望

例. CF518D IIya and Escalator

【题意简化】

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

$(1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1)$

• 定义法求期望

例. atcoder abc263 E-Sugoroku 3

【题意简化】

一共有 $N$ 个格子编号 $1$ 到 $N$。有一个人站在 $1$ 号格子。

对于 $\forall i \in [1,N-1]$ 号格子有一个 $A_i + 1$ 面的骰子，写有 $0$ 到 $A_i$ 这些数。如果他掷到了 $j$，他将往前走 $j$ 格，走到 $i+j$ 号方格。

求走到 $N$ 号方格的期望次数。对 $998244353$ 取模。

$2 \le n \le 2\times 10^5,1 \le A_i\le n-i(1\le i \le n-1)$

例. POJ-2096 Collecting Bugs

【题意简化】

一个软件有 $s(\le 1000)$ 个子系统，会产生 $n(\le 1000)$ 种 bug。某人一天发现一个 bug，这个 bug 属于某种 bug 分类，也属于某个子系统。每个 bug 属于某个子系统的概率是 $\frac{1}{s}$，属于某种 bug 分类的概率是 $\frac{1}{n}$ 。求发现 $n$ 种 bug，且 $s$ 个子系统都找到 bug 的期望天数。

例. NOIP2016 换教室

【题意简化】

学校有 $v(\le 300)$ 个上课地点，总 $n(\le 2000)$ 节课第 $i$ 节课同时在 $c_i(\le v)$ 和 $d_i(\le v)$ 教室讲(内容相同)，所有上课地点之间路径长度已知，保证任意两个教室相互可达。

你有不超过 $m(\le 2000)$ 次申请从班级 $c_i$ 换到 $d_i$ 上课， 申请成功的概率是 $k_i(0\le k_i \le 1)$ ,代价是 $c_i$ 到 $d_i$ 的最短距离。 即正常情况在 $c_i$ 教室上课，第 $i$ 节课申请换教室，会有 $k_i$ 的概率换到 $d_i$ 上课。

申请哪几门课程可以因在教室间移动耗费的体力值的总和的期望值最小，请求出这个最小值。

• “线性dp+期望” 经典题

例. P1654 OSU!

【题意简化】

一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$ ，失败对应 $0$， $n$ 次操作对应 $1$ 个长度为 $n$ 的 0-1 串。在这个串中连续的 $x$ 个 $1$ 可以获得 $x^3$ 的分数，这 $x$ 个 $1$ 不能被其他连续的 $1$ 所包含(也就是极长的一串 1)。最后得分就是每次获得的分数的总和。

现在给出 $n(\le 10^5)$ ，以及每个操作的成功率 $p_i(1\le p_i\le 1)$,请你输出期望得分，输出四舍五入后保留 1 位小数。

【分析】：

游戏长度与连续的 $1$ 的长度有关

$E(x)_i$ 表示以 $i$ 结尾连击长度（连续 1 的后缀长度）的期望， $E(x^2)_{i}$ 以 $i$ 结尾连击数的平方的期望，$E(f)_i$ 以 $i$ 结尾总得分期望

$E(x)_i=(p_i)*(E(x)_{i-1}+1)+(1-p_i)*0=p_i(E(x)_{i-1}+1)$

期望只有线性性质，$E(x^2)\ne E^2(x)$ , 只能推导：

$E(x^2)_i = p_i*E((x+1)^2)_{i-1}=p_i*(E(x^2)_{i-1}+2E(x)_{i-1}+1)$

假设第 $i$ 次操作成功，产生长度为 $x$ 的概率为 $P_x$ , 那么对于每一个 $x$ ,对分数产生 $(x+1)^3-x^3=3x^2+3x+1$ 的贡献。 第 $i$ 次操作成功有 $p_i$ 的概率，可以让得分增加如上的贡献，有：

$E(f)_i=E(f)_{i-1}+p_i(\sum_{x=0}^{i-1}{P_x*(3x^2+3x+1)})$

由于 $\sum_{x=0}^{i-1}P_x*x^2=E(x^2)_{i-1}$ 且 $E_{x=0}^{i-1}P_x*x=E(x)_{i-1}$ ，得到：

$E(f)_i=E(f)_{i-1}+p_i(3*E(x^2)_{i-1}+3*E(x)_{i-1}+1)$

例. CF280C Game on Tree

【题意简化】

给定一颗有根树，结点编号从 $1$ 到 $n(1\le n \le 10^5)$ ，根结点为 $1$ 。对于每次操作，等概率的选择一个尚未被删除的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。需要求出删除所有结点的期望操作次数，保留不少于 $6$ 位小数。

例. P2221 HAOI2012 高速公路

例. P2473 [SCOI2008] 奖励关

例. P4550 收集邮票

例. P3239 [HNOI2015] 亚瑟王

---

带有后效性期望问题*

例. CF24D Broken robot

例. P3232 [HNOI2013] 游走

Luogu P4457 [BJOI2018]治疗之雨

HDU4418 Time Travel

---

学习完毕

{{ select(1) }}

• YES
• NO