Link

Solution

要求立方和的期望值。考虑一个新的1对于答案的贡献。假设前面已经有x个1了 $(x+1)^3=x^3+3x^2+3x+1$ 即，对于期望已经存在 $x$ 个1的连续子串，加入一个1对答案的贡献为 $\Delta=3x^2+3x+1$ 所以，需要维护一个 $x^2$ 的期望和一个 $x$ 的期望。而 $x^2$ 的期望也类似。

Tips

$E(x^n)\neq E(x)^n$ ，因此要维护一个高次项的期望可以通过多项式展开转化成维护低次式的期望再相加。根据期望的线性性，这样做是正确的。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+1;
typedef long double ld;
int main()
{
	//freopen("input","r",stdin);
	static ld f[MAXN],exsq[MAXN],ex[MAXN];
	//f表示答案 exsq表示连续x^2的EXP ex表示连续x的exp
	int n;red(n);
	double cur;scanf("%lf",&cur);
	exsq[1]=ex[1]=f[1]=cur;
	for(int i=2;i<=n;i++)
	{
		scanf("%lf",&cur);
		//ex[i]=ex[i-1]+cur;
		ex[i]=cur*(ex[i-1]+1);
		//exsq[i]=exsq[i-1]+cur*(2*ex[i]+1);
		exsq[i]=cur*(exsq[i-1]+2*ex[i-1]+1);
		//f[i]=f[i-1]+cur*(3*exsq[i]+3*ex[i]+1);
		f[i]=f[i-1]+cur*(3*exsq[i-1]+3*ex[i-1]+1);
	}
	printf("%.1lf\n",(double)f[n]);
	return 0;
}