概率与期望

在做期望题时，一般都会用到期望的线性性.  

即 $\mathrm{E(X+Y)=E(X)+E(Y)}$.   

除此之外，还需知道条件期望公式 $\mathrm{E(X|Y)}$, 即 $\mathrm{Y}$ 为样本空间的期望.    

然后有 $\mathrm{P(A)E(X|A)=\sum xP((X=x) \bigcap A_{i}}$

如果想不清楚具体过程不妨列出全集，要求的东西，最后用条件期望整合到一起.   

 

例题：luoguP1654 OSU!

$\mathrm{ans=E(X)}$.

$\mathrm{X}$ 表示所有可能的 01 串的情况，为全集.  

那么，每个全集就是一些以 $\mathrm{r}$ 为右端点的极长 $1$ 的立方和.  

$\mathrm{X[i]=\sum len[r]^3}$.   

所以 $\mathrm{ E(X)=\sum E(len[r]^3) }$

这个可以用 $\mathrm{E(len[r-1]^3)}$ 来推到当前的 $\mathrm{r}$.  

然后就用条件期望整合：值为 $\mathrm{r-1}$ + 1 的期望立方和，概率为当前 $\mathrm{r=1}$.  

最后扫一遍即可.   

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100009 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int n ; 
double p[N],len1[N],len2[N],len3[N]; 
int main() {
    // setIO("input");
    scanf("%d",&n);    
    for(int i=1;i<=n;++i) {
        scanf("%lf",&p[i]); 
    }
    p[n + 1] = 0; 
    double ans = 0.0; 
    for(int i=1;i<=n;++i) {
        len1[i] = (len1[i-1] + 1) * p[i]; 
        len2[i] = (len2[i-1] + 1 + 2 * len1[i - 1]) * p[i];  
        len3[i] = (len3[i-1] + 1 + 3 * len1[i - 1] + 3 * len2[i - 1]) * p[i];  
        ans += len3[i] * (1 - p[i + 1]);  
    }
    printf("%.1f\n", ans); 
    return 0; 
}