之前做tyvj1952Easy（给定一个序列，每个位置有一定的概率是1或0，求极长连续1的长度平方期望）,用的做法是求出“全1子串的期望个数”.假如每一段极长连续1分别长x1,x2,x3…要求的答案为sigma{xi^2},全1子串的期望个数即为sigma{(xi+1)*xi/2},和sigma{xi}的期望（即1的个数的期望）加加减减就出来答案了。

Bzoj4318的题意同上，不过要求立方和的期望。做法是分别考虑每个位置的期望贡献。

即：111后加一个1的贡献为4*4-3*3=7,1111后加一个1的贡献为5*5-4*4=9

也就是说，在一段长度为x的1后面加一个1，贡献为(x+1)^3-x^3=3*x^2+3^x+1,只要算出在每个位置结尾的全1子串的长度期望和长度平方的期望即可。而全1子串的长度平方期望也可以考虑每个1的期望贡献2x+1,由长度的期望推出即可。

那么Tyvj1952也可以分别考虑每个位置的期望贡献(x+1)^2-x^2=2x+1了，只要维护在每个位置结尾的全1子串期望长度即可。

#include
     
      #include
      
       int main(){    int n;scanf("%d",&n);    char ch;    double x1=0,x2=0,p;    for(int i=1;i<=n;++i){        while(ch=getchar(),!isgraph(ch));        if(ch=='?')p=0.5;        else if(ch=='o')p=1;        else p=0;        x2+=p*(2*x1+1);        x1=p*(x1+1);    }    printf("%.4f\n",x2);    return 0;}
      
     

#include
     
      int main(){    int n;scanf("%d",&n);    double x1=0,x2=0,x3=0;//结尾连续长度的一次方和平方的期望以及总共的长度立方的期望    double x;    for(int i=1;i<=n;++i){        scanf("%lf",&x);        x3+=(3*x2+3*x1+1)*x;               x2=x*(x2+2*x1+1);        x1=x*(1+x1);//x的概率，x1长度变为 x1+1；(1-x)的概率，长度变为0    }    printf("%.1f\n",x3);    return 0;}