BZOJ 4318: OSU!

我们考虑

$E(xi + eta) = Exi + Eeta$

$E(xi + eta)^2 = Exi^2 + 2 cdot Exi cdot Eeta + Eeta^2$

$E(xi + eta)^3 = Exi^3 + 3 cdot Exi cdot Eeta ^2 + 3 cdot Exi^2 cdot Eeta + 3$

我们令

$f[i]  表示以i为结尾并且最后一位为1的数学期望$

$g[i] 表示 平方$

$h[i]  表示立方$

再考虑 对于前面$i位的结果，我们都已经知道，当再添加一位的时候$

$如果在当前位添加0，那么期望 = 权值 cdot 概率   此时的概率为 1 - p[i]  权值就是 h[i - 1]$

$那如果添加1，依据上述公式递推即可$

#include <bits/stdc++.h>
using namespace std;

#define N 100010
int n;
double p[N], f[N], g[N], h[N];

void Run()
{
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; ++i) scanf("%lf", p + i);
        for (int i = 1; i <= n; ++i)
        {
            f[i] = p[i] * (f[i - 1] + 1);
            g[i] = p[i] * (g[i - 1] + 2 * f[i - 1] + 1);
            h[i] = p[i] * (h[i - 1] + 3 * g[i - 1] + 3 * f[i - 1] + 1) + (1 - p[i]) * h[i - 1];
        }
        printf("%.1f
", h[n]);
    }
}

int main()
{
    #ifdef LOCAL
        freopen("Test.in", "r", stdin);
    #endif 

    Run();
    return 0;
}