之前做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<cstdio>
#include<cctype>
int main(){
int n;scanf("%d",&n);
char ch;
double x1=,x2=,p;
for(int i=;i<=n;++i){
while(ch=getchar(),!isgraph(ch));
if(ch=='?')p=0.5;
else if(ch=='o')p=;
else p=;
x2+=p*(*x1+);
x1=p*(x1+);
}
printf("%.4f\n",x2);
return ;
}
#include<cstdio>
int main(){
int n;scanf("%d",&n);
double x1=,x2=,x3=;//结尾连续长度的一次方和平方的期望以及总共的长度立方的期望
double x;
for(int i=;i<=n;++i){
scanf("%lf",&x);
x3+=(*x2+*x1+)*x;
x2=x*(x2+*x1+);
x1=x*(+x1);//x的概率，x1长度变为 x1+1；(1-x)的概率，长度变为0
}
printf("%.1f\n",x3);
return ;
}