一.数学期望的概念
「学习笔记」期望问题 是学习期望概率dp的基础，建议学习后再来阅读该学习笔记。
数学期望（简称期望），是试验中每次可能结果的概率乘以其结果的总和，它反映了随机变量平均取值的大小。
数学期望可以用加权平均数来理解，可能取值就是初始数据，概率就是每个数的权，此时期望就是加权平均数。
二.数学期望的计算公式
对于随机变量 \(X\)，它有 \(n\) 种可能的取值，取值为 \(x_i\) 的概率为 \(P(x_i)\)，那么它的数学期望 \(E(X)=\Sigma _{i=1}^{n} x_i P(x_i)\)。
举个例子：给定一个随机变量 \(X\)，它有六种可能的取值，分别是 \(1,2,3,4,5,6\)，且取每个值得概率是一样的，那么 \(E(X)=\frac{1}{6}×1+\frac{1}{6}×2+\frac{1}{6}×3+\frac{1}{6}×4+\frac{1}{6}×5+\frac{1}{6}×6=\frac{7}{2}\)。
三.数学期望的性质
设 \(A,B,C\) 为常数， \(X,Y\) 为随机变量，那么有：
- \(E(C)=C\)；
- \(E(CX)=CE(X)\)；
- 重点：\(E(X+Y)=E(X)+E(Y)\)，线性性；
- \(X,Y\) 互相独立时， \(E(XY)=E(X)E(Y)\)；
- 结合上列性质，得出 \(X,Y\) 互相独立时 \(E(AX+BY)=AE(X)+BE(Y)\)。
四.期望dp
求解达到某一目标的期望代价：因为最终的代价我们不知道，所以需要倒序求解。
设 \(f_{i,j}\) 为在 \((i,j)\) 这个状态实现目标的期望代价（相当于相距目标多少）。
当然我们也可以采用正序求解，只需要将状态的意义确定，符合要求，就可以求解。
五.例题讲解
Ybtoj【例题1】路径长度
P4316 绿豆蛙的归宿
因为已知最终状态，按照期望dp的想法，我们采用逆推。
设有向边 \(x\to y\)，那么有 \(f_x=(\frac{1}{deg_x})\Sigma f_y + w_{x\to y}\)。
因为反向建边，所以我们要把 \(x,y\) 颠倒过来。
在 \(DAG\) 上进行拓扑排序即可转移状态。
核心代码：
queue <int> q;
q.push (n);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i=head[u]; i; i = e[i].from) {
int v = e[i].to;
f[v] += (f[u] + e[i].w) / dg[v];
if(--in[v] == 0) {
q.push (v);
}
}
}
Ybtoj【例题2】乘坐电梯
CF518D Ilya and Escalator
设 \(f_{i,j}\) 为在第 \(i\) 个人，第 \(j\) 秒时电梯上的期望人数。
那么，易得 \(f_{i,j}=(1-p)×f_{i, j - 1} + p×(f_{i-1,j-1}+1)\)。
最后输出 \(f_{n,t}\) 即可。
Ybtoj【例题3】期望收益
P1365 WJMZBMR打osu! / Easy
先思考一下，在连续 \(a\) 个 \(o\) 后面再加一个 \(o\)，会对答案产生多少贡献？
显然，会多贡献 \((a+1)^2-a^2=a^2+1+2a-a^2=2a+1\)。
当处理到第 \(i\) 位时，我们可以知道以第 \(i\) 位为结尾的连续 \(o\) 的期望长度，根据 连续 \(o\) 的期望长度，就可以轻松算出期望分数。
核心代码：
for (int i = 1; i <= n; i++) {
if (c[i] == 'o') {
ans += len * 2 + 1;//一定是，累计贡献。
len++;//同上。
}
else if (c[i] == 'x') {
len = 0;//一定不是，期望长度归0。
}
else {
ans += (len * 2 + 1) / 2;//有一半的概率不是o，所以要除以2。
len = (len + 1) / 2;//同上。
}
}
Ybtoj【例题4】期望分数
P1654 OSU!
和上题相似，但是指数为 \(3\)。
也思考一下，在连续 \(a\) 个 \(o\) 后面再加一个 \(o\)，会对答案产生多少贡献？
计算出会多贡献 \((a+1)^3-a^3=a^3+3a^2+3a+1-a^3=3a^2+3a+1\)。
设 \(E(X_i)\) 为在第 \(i\) 位得的分数期望，我们思考一下 \(E(X_i)\) 和 \(E(X_{i+1})\) 的关系。
假设在 \(i\) 位置连续 \(1\) 串长度为 \(l\) 的概率为 \(p_{l}\)，在 \(i+1\) 位置是 \(1\) 的概率为 \(P\) ，那么对于每一个单独的 \(l\) 它都有 \(P\) 的概率对分数产生 \((3l^{2}+3l+1)\)的额外贡献。
我们把所有可能的 \(l\) 一起考虑，就可以得到这个式子：
\(E(X_{i+1})=E(X_i)+P×\Sigma_{l=0}^{i}p_l(3l^2+3l+1)\)。
然后我们将式子转化为：
\(E(X_{i+1})=E(X_i)+P×(3E(l_i^2)+3E(l_i)+1)\)
接下来维护 \(E(l)\) 和 \(E(l^2)\)。
于是我们可以这么算：
\(E(l_{i+1}=P×(E(l_i)+1)\)
\(E(l_{i+1}^2=P×(E(l_i^2)+2E(l_i)+1)\)。
然后我们递推，用三个变量存储即可。
核心代码：
for (int i = 1; i <= n; i ++) {
ans += (3 * len2 + 3 * len1 + 1) * p[i];
len2 = (len2 + 2 * len1 + 1) * p[i];
len1 = (len1 + 1) * p[i];
}
printf ("%.1lf", ans);