http://codeforces.com/contest/236/problem/D
题意，一个由xo组成的字符串，连续的o的个数的平方算入权值，长度为n的序列，给出每个字符为o的概率，求所有序列的权值的期望。
思路：
对于任何一个o，相对于所在的序列，会有自己固定的权值
首先要知道（a+1）^2=a^2+2*a+1
例如：对于五个o的价值是5*5=25，
那么可以从第一个开始考虑，
第一个o价值是1
第二个o相当于对于一个o的序列加上了一个o，即增加的价值为（1+1)^2-1^2=1*2+1=3
第三个o相当于对于两个o的序列加上了一个o，即增加的价值为（2+1)^2-2^2=2*2+1=5
第四个o……，增加的价值为3*2+1=7
第五个o……，增加的价值为4*2+1=9
总计是25，所以可以看出可行！
再用到的一个知识点就是概率加权，学过概率还是很好理解的，就是要把o出现的概率加上，就可以算出前面连续出现的o的个数
跟着上面结合，一步步推出来，带上p，提个公因式即可~
#include<bits/stdc++.h> using namespace std; double p[100005]; double ans,a; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf",&p[i]); ans=p[1]; a=1; for(int i=2;i<=n;i++) { ans+=p[i]*(p[i-1]*(a*2+1)+(1-p[i-1])); a=p[i-1]*(a+1)+(1-p[i-1]); } printf("%.15f\n",ans); }
