概述

一般是先写出转移方程(组),然后移项
其中期望只能逆推,概率一般为正推。

期望性质

  • $E(x) = \sum_{k=1}^n x_kP(x_k)$
  • $E(ax + by + c) = aE(x) + bE(y) + c$ (期望的线性)
  • $E(xy) = E(x)E(y)$ (若x和y相互独立)
  • $Var(x) = E(x^2) - E^2(x)$ (方差)

题目

概率

poj3744

一个数轴上有n个地雷,起点位于1,每次可以走一步(概率为p)或两步(概率为1-p)
求安全通过的概率

概率DP+矩阵快速幂
递推式为 $d_i = pd_{i-1} + (1-p)d_{i-2}$,可以用矩阵快速幂求解
我们将每两段地雷分段,设长度为len,可以求出恰好踩到地雷概率$d_{len}$
然后最后答案为所有 $1-d_{len}$ 乘起来

poj2151

t支队伍,m道题,每队有不同的概率解出每道题。
求所有所有队伍至少过一题,至少有一支队伍过至少过n题的概率

P(至少有一支队伍过一题) - P(所有队伍都过至少一题至多n-1题)

cf105 D

有w个白球,b个黑球,P先手,D后手,然后随机跳出一个,谁先取到白球谁赢
若谁都没有取到则D赢,求P赢的概率

$d_{i,j}$ 表示剩余i个白球和j个黑球的概率

$d_{i,j} = \begin{cases} \frac{(j+1)d_{i,j+1}}{i+j+1} & (w+b-(i+j)) \mod 3 < 2 \\ \frac{(i+1)d_{i+1,j}}{i+j+1} + \frac{(j+1)d_{i,j+1}}{i+j+1}& (w+b-(i+j)) \mod 3 = 2 \end{cases}$
$ans = \sum_{i>0 \; (w+b-(i+j)) \mod 3 = 0 } \frac{id_{i,j}}{i+j}$

poj3071

$2^n$支队伍的淘汰赛,$p_{i,j}$表示i打败j的概率,问最后谁是冠军的概率最大

类似三角形dp

期望

poj2096

概率dp入门
求期望用逆推 d[i][j] 表示所选bug,有i个分类,分别属于j个子系统
其可以推到
d[i][j] = (i/n+j/s)d[i][j] + ((n-i)/n+j/s)d[i+1][j] + (i/n+s-j/s)d[i][j+1] + (n-i)/nd[i+1][j+1]
四个阶段
然后将递推式移项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>

const int maxn = 1010;
double d[maxn][maxn];
int n,s;

int main()
{
while(scanf("%d %d",&n,&s)==2)
{
d[n][s] = 0;
for(int i=n;i>=0;--i)
{
for(int j=s;j>=0;--j)
{
if(i==n && j==s) continue;
d[i][j] = ((n-i)*j*d[i+1][j] + i*(s-j)*d[i][j+1] + (n-i)*(s-j)*d[i+1][j+1] + n*s)/(n*s - i*j);
}
}
printf("%.4f\n",d[0][0]);
}
return 0;
}

hdu4405

按照题目意思写转移即可

vijos1675(NOI2005)

n次bfs处理出p[u,v]表示从u到v的最短距离的编号最小的点。
d[u,v] 表示从u到v吃掉可可需要时间的期望

$$d_{u,v} = \frac{\sum_{(w link v) or (w is v)} d_{p[p[u,v],v],w}}{deg[v]+1} + 1$$

若p[u][v] = v 或 p[p[u][v]][v] = v 说明已经相遇,则直接返回1 , 若 u = v 则返回 0

hdu4089

根据题意列出转移方程,并解之
注意精度问题,p4 < eps时应输出0

hdu4035

一棵树,从根出发,每次有$k_i、e_i、1-k_i-e_i$概率回到根,结束,随机选一条相连路径

求走出迷宫的步数期望

待定系数,从树的叶子结点推到根

期望线性

bzoj4318

长度为n(1e5)的01串,每位有$p_i$的概率为0,连续长度为x的1得分为$x^3$
求最后得分的期望

设 $f(i)$ 为前i个字符的得分期望

假设上一个串的长度期望为x

由期望的线性性,新增得分期望则为
$E_{(x+1)^3 - x^3} = 3E_{x^2} + 3E_{x} + 1$

$f(i) = f(i-1) + p(i)(3E_{x^2} + 3E_{x} + 1)$

仍然考虑期望线性性
$E_{x+1} = E_x + 1$
$E_x(i) = p(i)(E_x(i-1) + 1)$

$E_{(x+1)^2} = E_{x^2} + 2E_x + 1$
$E_{x^2}(i) = pi + 2E_x(i-1) + 1)$

此时,$E_{x}(i)$,$E_{x^2}(i)$,$f(i)$均可以线性递推

O(1)/O(n) 公式

sgu495

n个盒子,初始每个盒子都有一个球
取m次,问最后盒子中所剩球的期望

每个球不被取走的概率为 ((n-1)/n)^m
不被取走球数的期望则为 n((n-1)/n)^m
所以最后答案为 n - n((n-1)/n)^m

WUST2016 E

n个点,每个点得分概率为p,连续x个点总得分为1+2+…+x,求n个点总得分期望

1 2 3 …
p
p p^2
p p^2 p^3

$E = p^n + 2p^{n-1} + … + np$

然后用错位相减法求和
$pE - E = p^{n+1} + … + p^2 - np$
$E = \frac{\frac{p^2 - p^{n+2}}{1-p} - np}{p-1}$

p = 1时应特判…

cf351 E

取到的概率 $p_i$ ,取的期望次数为 $\frac{1}{p_i}$

精度收敛

cf-643e

一棵树,选择一棵子树,所有的边有1/2的概率被破坏
q个询问,对于询问1,添加一个结点到结点u
对于询问2,选择结点u的子树,问子树被破坏后深度的期望
询问2之互不影响

设$f(u,d)$为子树深度 <= d的概率
答案就是 $\sum_{i=1}^{maxd} i(f(u,i) - f(u,i-1))$
而$f(u,d) = \prod_{v \in children(u)} \frac{1+f(v,d-1)}{2}$
对于叶子结点$f(u,i) = 1$,新加入一个结点,只会影响到其所有祖先
而这个式子是收敛的,我们向上更新大概60层就可以满足精度要求了

复杂度$O(60q)$

精度问题

几乎所有的概率dp都会涉及精度问题

以简单的hdu3853为例

求从RC的矩阵左上角走到右下角的期望操作2,每次操作分别有p1,p2,p3的概率不动、向右、向下

$d_{i,j} = p_1d_{i,j} + p_2d_{i,j+1} + p_3d_{i+1,j} + 2$
$d_{i,j} = \frac{p_2d_{i,j+1}}{1-p_1} + \frac{p_3d_{i+1,j}}{1-p_1} + \frac{2}{1-p_1}$

当$1-p_1$极小时,答案会大于题目保证的1e6,这就说明该点永远都不会到达,该点期望应记为0