Description：

给定一个长度为 $n$ 的 $01$ 串，第 $i$ 个位置有 $a_i$ 的概率为 $1$ ，最终得分为 $01$ 串中所有连在一起 $1$ 的长度的立方和，求得分的期望。

$N \le 10^5$

Solution：

题意大概就是求所有连续的 $1$ 的长度的三次方和的期望，一眼看非常不可做，而三次方的期望不等于期望的三次方，于是不难想到维护 $l1[i]$ 表示截止到 $i$ 的长度的期望， $l2[i]$ 表示截止到 $i$ 的长度的平方的期望， $l3[i]$ 表示截止到 $i$ 的长度的立方的期望，于是有： $$ l_1[i]=a_i\times (l_1[i-1]+1)+(1-a_i)\times 0=a_i\times (l_1[i-1]+1) $$

$$ l_2[i]=E(l_1[i]^2)=a_i\times E((l_1[i-1]+1)^2)+(1-a_i)\times 0=a_i\times\Bigl(E(l_1[i-1]^2)+2\times E(l_1[i-1])+1\Bigr)=a_i\times (l_2[i-1]+2\times l_1[i-1]+1) $$

$l_3[i]=E(l_1[i]^3)=a_i\times E((l_1[i-1]+1)^3)=a_i\times (E(l_1[i-1]^3)+3\times E(l_1[i-1]^2)+3\times E(l_1[i-1])+1) $

$ans[i]=ans[i-1]+l_3[i]-a[i]\times l_3[i-1]$ 代表如果连起来了，那么要减掉计算了两次的价值。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

double a[MAXN],l1[MAXN],l2[MAXN],l3[MAXN],ans[MAXN];

int main()

{

    scanf("%d",&n);

    for(int i = 1;i <= n;++i)

    {

        cin >> a[i];

        l1[i] = a[i] * (l1[i - 1] + 1);

        l2[i] = a[i] * (l2[i - 1] + 2 * l1[i - 1] + 1);

        l3[i] = a[i] * (l3[i - 1] + 3 * l2[i - 1] + 3 * l1[i - 1] + 1);

        ans[i] = ans[i - 1] + l3[i] - l3[i - 1] * a[i];

    }

    printf("%.1f\n",ans[n]);

    return 0;

}