概率/期望类 DP
OI-wiki Intro
P1365 WJMZBMR打osu! / Easy
更好的题解
强调对于离散型随机变量的全期望公式的使用、期望的线性性。笔者水平很有限，只能大致给出很小一部分模糊的定义：
对于离散型随机变量（不考虑连续的实数域毕竟积分超出了学习范围）对于每个事件 \(X\) 对应概率 \(P\) 有 \(p_i=P\{x_i=X\}\)，整体期望 \(\sum x_i p_i\) （当且仅当其绝对收敛），记其值为 \(EX\)。
性质1：\(E(X+Y)=EX+EY\)。
性质2：\(E(XY)=EX\cdot EY\)（\(XY\) 是 \(X,Y\) 组合相乘后的事件）
我们的期望拆分依据全期望公式展开，本文不进行详细介绍。
- \(L_i\) 表示做完前 \(i\) 次点击所获得的 combo。特别地，如果第 \(i\) 位是
?，分别有 \(\frac{1}{2}\) 的概率取到 \(0\) 和 \(L_{i-1}+1\)。 - \(F_i\) 表示做完前 \(i\) 次点击所获得的得分，如果取到
?，转移就是各有 \(\frac{1}{2}\) 的概率取到 \(F_{i-1}\) 与 \(F_{i-1}+L_i^2-L_{i-1}^2=F_{i-1}+(L_{i-1}+1)^2-L_{i-1}^2=F_{i-1}+2L_{i-1}+1\)，特别地，这里对 \(L_{i-1}\) 做了钦定其 \(+1\) 的指示。
我们发现了，上面定义的两个变量都是随机变量，就是说，我们不能确保它有一个确定的取值，但是每一个取值都会有一个概率，所以我们不妨也给他们直接计算期望 \(E(F_i),E(L_i)\)，由性质1，我们会发现都计算期望的情况下是有普适且正确的转移的，这来源于期望的线性性，也就是为什么我们能够直接用 \(L_{i-1}\) 的期望转移 \(F_i\) 的原因。
本题中存在随机变量 \(\Delta i=F_i-F_{i-1}\)，取 o 时 \(\Delta i=2L_{i-1}+1\)，取 x 时 \(\Delta i=0\)，取 ? 时各有 \(\frac{1}{2}\) 的概率取到上面两个之一。
本题中需要解决的是取 ? 的问题，我们不妨设一个 \(\texttt{len}\) 记录当前 combo 的期望，然后用一个 \(E(F_i)\) 来转移 \(E(F_i)=E(F_{i-1}+\Delta i)=E(F_{i-1})+E(\Delta i)\)，即可以写成一个前缀和的形式，考虑 \(E(\Delta i)\) 的单独计算即可。根据定义，\(E(\Delta i)=\sum x_j p_j=\frac{1}{2}\times 0+\frac{1}{2}\times(2E(L_{i-1})+1)=E(L_{i-1})+\frac{1}{2}\)，这样线性递推就解决了本题。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n;
char s[N];
long double f[N],L;
int main(){scanf("%d",&n);scanf("%s",s+1);f[0]=0;for(int i=1;i<=n;i++){if(s[i]=='o')f[i]=f[i-1]+2*L+1,L++;else if(s[i]=='x')f[i]=f[i-1],L=0;else f[i]=f[i-1]+L+0.5,L=(L+1)/2;}printf("%.4Lf",f[n]);return 0;
}
P3232 [HNOI2013] 游走
本题的期望有点特殊，因为在无向有环连通图中转移不是线性的，可能是环形的。具体来说，我们先对每个节点（除 \(n\)）考虑期望经过次数 \(E(x)\)，然后就可以通过每条边的 \(E(u,v)=\frac{E(u)}{deg_u}(u\neq n)+\frac{E(v)}{deg_v}(v\neq n)\)（分别表示从 \(u\) 到 \(v\) 和 \(v\) 到 \(u\)），考虑的出发角度是一个节点会任选 \(deg_i\) 条与之相连的边中（包括重边、自环）等概率任意一条，然后按期望从大到小的顺序从小到大赋边编号即可。
这样我们同样可以推出点期望次数转移 \(E(x)=\begin{cases}\sum_{(x,i)\in E}\frac{E(i)}{deg_i} +1 & x=1\\\sum_{(x,i)\in E}\frac{E(i)}{deg_i}& \text{otherwise}\end{cases}\)，然后可以用高斯消元求解每个 \(E(x)\)，这题就做完了。
#include<bits/stdc++.h>
using namespace std;
const int N=505;
long double f[N][N],ans;
int n,m,deg[N];
struct Edge{int u,v;long double w;}e[125005];
vector<int>G[N];
bool cmp(Edge x,Edge y){return x.w>y.w;}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&e[i].u,&e[i].v),deg[e[i].u]++,deg[e[i].v]++;G[e[i].u].push_back(e[i].v);G[e[i].v].push_back(e[i].u);}for(int i=1;i<n;i++){if(i==1)f[i][n]=-1;for(int j:G[i])if(j!=n)f[i][j]+=1.0/deg[j];f[i][i]--;}for(int i=1;i<=n-1;i++){int pos=0;for(int j=i;j<=n-1;j++)if(f[j][i]){pos=j;break;}swap(f[i],f[pos]);long double num=f[i][i];for(int j=1;j<=n;j++)f[i][j]/=num;for(int j=1;j<=n-1;j++){if(j==i)continue;if(f[j][i]){num=f[j][i]/f[i][i];for(int k=1;k<=n;k++)f[j][k]-=num*f[i][k];}}}for(int i=1;i<=m;i++)e[i].w=f[e[i].u][n]/deg[e[i].u]+f[e[i].v][n]/deg[e[i].v];sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++)ans+=e[i].w*i;printf("%.3Lf",ans);return 0;
}