期望
\(x\) 的期望 \(E(x)\) 表示平均情况下 \(x\) 的值。
令 \(C\) 表示常数， \(X\) 和 \(Y\) 表示两个随机变量。
-
\(E(C)=C\)
-
\(E(C \times X)=C \times E(X)\)
-
\(E(X+Y)=E(X)+E(Y)\) 期望的线性性
-
\(E(XY)\) 不一定等于 \(E(X) \times E(Y)\)
期望练习：
题意：
\(n\) 个格子从左往右排成一排，\(m\) 次操作。
每次操作随机选择一个区间 \([l,r]\) ，将里面所有格子涂黑。
求 \(m\) 次操作完毕后，被涂黑的格子数量的期望。
\(solution\)：
期望的线性性，答案等于每个格子被涂黑的概率之和。
对于某个格子，假设一次操作涂黑它的概率为 \(p\) ，则 \(m\) 次操作涂黑它的概率为 \(1-(1-p)^m\)。
期望（概率）DP
题意：
\(n\) 个点 \(m\) 条边的有向无环图，保证 \(1\) 可以到达每个点，且每个点可以到达 \(n\) 号点。如果现在在 \(x\) ，\(x\) 连了 \(d\) 条边出去，那么会以 \(\dfrac{1}{d}\) 的概率随机选择一条边走过去。
求 \(1\) 游走到 \(n\) 的期望步数。
$n \le 100000 $ ，\(m \le 200000\)
\(solution\) ：
记忆化搜索。
设 \(e[x]\) 表示 \(x\) 走到 \(n\) 的期望步数。
\[e[n]=0 \] \[e[x]= 1 + \dfrac{\sum_{y}^{y \in son[x]}e[y]}{d[x]} \]复杂度：\(O(n + m)\) 。
$\texttt{code}$
void dfs(ll x)
{
if(dp[x]!=-1) return;
ll cnt=0;
for(ll i=hea[x];i;i=nex[i])
{
dfs(ver[i]);
cnt+=dp[ver[i]];
}
dp[x]=(cnt*inv[x]+1)%mod;
}
for(ll i=1;i<=m;i++)
{
u=rd(),v=rd();
add(u,v),outd[u]+=1;
}
for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i],mod-2);
dfs(1);
printf("%lld\n",dp[1]);
题意：
\(n\) 个点 \(m\) 条边的有向无环图，保证 \(1\) 可以到达每个点，且每个点可以到达 \(n\) 号点。如果现在在 \(x\) ，\(x\) 连了 \(d\) 条边出去，那么会以 \(\dfrac{1}{d+1}\) 的概率随机选择一条边走过去，或者以 \(\dfrac{1}{d+1}\) 的概率待在 \(x\) 点不动。
求 \(1\) 游走到 \(n\) 的期望步数。
\(n \le 100000\) ，\(m \le 200000\)
\(solution\) ：
\[e[x]=\dfrac{e[x]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \]有 \(e[x]\) 怎么办？化简！
\[e[x] \times (d[x]+1)=e[x]+d[x]+1+\sum_{y}^{y \in son[x]}{e[y]} \] \[e[x] \times d[x]=d[x]+1+\sum_{y}^{y \in son[x]}{e[y]} \]结论：
\[e[x]=\dfrac{d[x]+1+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]} \]复杂度：\(O(n+m)\) 。
$\texttt{code}$
void dfs(ll x)
{
if(dp[x]!=-1) return;
ll cnt=0;
for(ll i=hea[x];i;i=nex[i])
{
dfs(ver[i]);
cnt+=dp[ver[i]];
}
dp[x]=(cnt+outd[x]+1)*inv[x]%mod;
}
for(ll i=1;i<=m;i++)
{
u=rd(),v=rd();
add(u,v),outd[u]+=1;
}
for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i],mod-2);
dfs(1);
printf("%lld\n",dp[1]);
题意：
\(n\) 个点 \(m\) 条边的有向无环图，保证 \(1\) 可以到达每个点，且每个点可以到达 \(n\) 号点。如果现在在 \(x\) ，\(x\) 连了 \(d\) 条边出去，那么会以 \(\dfrac{1}{d+1}\) 的概率随机选择一条边走过去，或者以 \(\dfrac{1}{d+1}\) 的概率回到 \(1\) 号点。
求 \(1\) 游走到 \(n\) 的期望步数。
\(n \le 100000\) ，\(m \le 200000\)
\(solution\) ：
\[e[x]=\dfrac{e[1]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \]有 \(e[1]\) 怎么办？另外定义转移方程！
设：
\[e[x]=f[x] * e[1]+g[x] \]则有：
\[e[1]=\dfrac{g[x]}{1-f[x]} \]带入转移方程式：
\[e[x]=\dfrac{e[1]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \] \[e[x] = \dfrac{e[1]+\sum_{y}^{y \in son[x]}{(f[y] \times e[1] + g[y])}}{d[x]+1}+1 \] \[e[x] = \begin{pmatrix}\dfrac{e[1]+\sum_{y}^{y \in son[x]}{f[y] \times e[1]}}{d[x]+1}\end{pmatrix} + \begin{pmatrix}1+\dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1}\end{pmatrix} \] \[e[x] = \begin{pmatrix}\dfrac{1+\sum_{y}^{y \in son[x]}{f[y]}}{d[x]+1}\end{pmatrix} \times e[1] + \begin{pmatrix}1 + \dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1} \end{pmatrix} \]因为 \(e[x]=f[x] * e[1]+g[x]\) ，所以最终可以得出结论：
\[f[x] = \dfrac{1+\sum_{y}^{y \in son[x]}{f[y]}}{d[x]+1} \] \[g[x] = 1 + \dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1} \] \[e[1]=\dfrac{g[x]}{1-f[x]} \]带入求值即可。
$\texttt{code}$
void dfs(ll x)
{
if(f[x]!=-1) return;
ll cntf=0,cntg=0;
for(ll i=hea[x];i;i=nex[i])
{
dfs(ver[i]);
cntf+=f[ver[i]];
cntg+=g[ver[i]];
}
f[x]=(cntf+1)*inv[x]%mod;
g[x]=(cntg*inv[x]%mod+1ll)%mod;
}
for(ll i=1;i<=m;i++)
{
u=rd(),v=rd();
add(u,v),outd[u]+=1;
}
for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i]+1,mod-2);
dfs(1);
printf("%lld\n",g[1]*Pow(((1-f[1]+mod)%mod+mod)%mod,mod-2)%mod);
其他习题
P1850 换教室
状态：设 \(dp[i][j][0/1]\) 来表示当前为第 \(i\) 个阶段，连同这一次已经用了 \(j\) 次换教室的机会，当前这次换 \((1)\) 不换 \((0)\) 的最小期望路程总和。
转移：
- 转移 \(dp[i][j][0]\) ：
dp[i][j][0]=fmin
(
dp[i-1][j][0] + dis[c[i-1]][c[i]],
dp[i-1][j][1] + p[i-1]*dis[d[i-1]][c[i]] + (1.0-p[i-1])*dis[c[i-1]][c[i]]
);
- 转移 \(dp[i][j][1]\) ：
dp[i][j][1]=fmin
(
dp[i-1][j-1][0] + p[i]*dis[c[i-1]][d[i]] + (1-p[i])*dis[c[i-1]][c[i]],
dp[i-1][j-1][1] +
p[i-1]*p[i]*dis[d[i-1]][d[i]] + p[i-1]*(1-p[i])*dis[d[i-1]][c[i]] +
(1-p[i-1])*p[i]*dis[c[i-1]][d[i]] + (1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]
);
难点：因为在上一次换教室时是 概率 交换，所以不一定会换，所以要把两种情况的都加上（上面写了）。
$\texttt{code}$
memset(dis,inf,sizeof(dis));
for(int i=1;i<=v;i++) dis[i][i]=0;
int x,y,eg;
for(int i=1;i<=e;i++) x=rd(),y=rd(),eg=rd(),dis[x][y]=dis[y][x]=min(dis[x][y],eg);
for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++)
dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=1;k++) dp[i][j][k]=1.0*inf;
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=min(i,m);j++)
{
dp[i][j][0]=fmin
(
dp[i-1][j][0] + dis[c[i-1]][c[i]],
dp[i-1][j][1] + p[i-1]*dis[d[i-1]][c[i]] + (1.0-p[i-1])*dis[c[i-1]][c[i]]
);
if(j!=0) dp[i][j][1]=fmin
(
dp[i-1][j-1][0] + p[i]*dis[c[i-1]][d[i]] + (1-p[i])*dis[c[i-1]][c[i]],
dp[i-1][j-1][1] +
p[i-1]*p[i]*dis[d[i-1]][d[i]] + p[i-1]*(1-p[i])*dis[d[i-1]][c[i]] +
(1-p[i-1])*p[i]*dis[c[i-1]][d[i]] + (1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]
);
}
}
ans=1.0*inf;
for(int j=0;j<=m;j++) for(int k=0;k<=1;k++) ans=fmin(ans,dp[n][j][k]);
printf("%.2lf\n",ans);