模板及讲解

数学期望

随机变量$X$的数学期望$E(X)$就是所有可能值按照概率加权的和。
$$E(X)=\sum_{i=1}^nx_ip_i$$

数学期望计算线性性质

$$E(aX+bY)=aE(X)+bE(Y)$$
$$E(XY)=E(X)+E(Y)$$

概率部分公式

($P(A|B)$表示$B$事件发生的条件下，事件$A$发生的概率。)
($P(AB)=P(A \cap B)$表示$A、B$同时发生的概率。)

1、
若$A、B$不相交，则$P(A \cup B) = P(A) + P(B)$
若$A、B$为事件，则$P(A \cup B) = P(A) + P(B) - P(AB)$(广义加法公式)

2、
若$A_1, A_2, …, A_3$互不相交，则
$P(A_1+A_2+…+A_n)=P(A_1) + P(A_2) +…P(A_n)$(加法原理)

3、
$A \in B$时$P(B-A)=P(B)-P(A)$(容斥原理)

4、
$P(AB)=0$时$P(AB) = P(A)(B)$(乘法原理)

全概率公式

$$P(A)=P(A|B_1) \times P(B_1) + P(A|B_2) \times P(B_2) + … + P(A|B_n) \times P(B_n)$$

常见题型

1、DP求期望(倒推, dp状态表示为从当前点到终态的期望)
Q: 求到达某目标(终态)的期望值。
解: 倒推, $dp[i]$为从$i$点到终态的期望。
例题:poj 2096
2、DP求概率1(顺推, 第i层j前进的概率)
Q: 求到达某目标(终态)的概率。
解: 顺推, $dp[i][j]$为在$i$层$j$前进的概率。
例题:poj 3071
3、DP求概率2(xx状态存在概率)
Q: 求到达某目标(终态)的概率。
解: 设$dp(i,j,k)$为状态为$(i,j,k)$的存在概率。
例题:Codeforces 540D
4、直接求期望
Q: 每个概率有一个权，求期望权。
解: 直接利用期望定义求解。
例题:AHSOFNU NOIP模拟-11 t3
5、记忆化搜索求期望
解: 从要求的状态向已知状态记忆化搜索。
例题:zoj 3640
6、最优策略分步取$min$
Q: 在最有策略下，xxx的最小期望
解: 分步取$min$。
例题: NOIP2016 Day2 T1, bzoj 1076