1. 题目

传送门=￣ω￣=

2. 题解

又一道 XZY 不会的简单概率期望题。

首先可以轻松算出以 $x$结尾的极大连续 1 的期望长度 $g _ x$

$g _ x=p _ x \times (g _ {x – 1} + 1)$

$p _ x$表示在 $x$这个位置打出 1 的概率

然后我们要注意到：

期望的平方不等于平方的期望

因为这里的期望中的两个事件是相关的（它们是同一件事情肯定相关呀），所以期望与概率不满足单纯的乘法关系。

那怎么办算期望长度的三次方呢？

连续长度为 $l$的期望是 $E(l)$，而我们要求的是 $E(l ^ 3)$，我们先求出 $E(l ^ 2)$吧。

设 $E[(l + 1) ^ 2] = E(l) + \Delta$

则：

$\Delta = E[(l + 1) ^ 2] – E(l)$
$=E[(l + 1) ^ 2 – l]$
$=E(l ^ 2 + 2l + 1 – l)$
$=E(l ^ 2 + l + 1)$
$=E(l ^ 2) + E(l) + 1$

即：

$E[(l + 1) ^ 2] = E(l ^ 2) + 2 E(l) + 1$

也就是说，我们设 $h _ x$为以 $x$结尾的极大连续 1 的长度的平方的期望

有：

$h _ x = p _ x \times (h _ {x – 1} + 2 g _ {x – 1} + 1)$

接着我们再求出 $E(l ^ 3)$：

设 $E[(l + 1) ^ 3]=E(l ^ 2) + \Delta$

则：

$\Delta = E[(l + 1) ^ 3] – E(l ^ 2)$
$=E[(l + 1) ^ 3 – l ^ 2]$
$=E(l ^ 3 + 3 l ^ 2 + 3 l + 1 – l ^ 2)$
$=E(l ^ 3 + 2l ^ 2 + 3 l + 1)$
$=E(l ^ 3) + 2 E(l ^ 2) + 3 E(l) + 1$

即：

$E[(l + 1) ^ 3] = E(l ^ 3) + 3 E(l ^ 2) + 3 E(l) + 1$

也就是说，我们设 $f _ x$为以 $x$结尾的极大连续 1 的长度的三次方的期望

有：

$f _ x = p _ x \times (f _ {x – 1} + 3 h _ {x – 1} + 3 g _ {x – 1} + 1)$

然后这题就做完惹。。。答案就是 $f _ n$

（另外还有简化版的这一题，参见 Easy BZOJ – 3450）

（另另外还有简化版的这一题，参见 CF235B Let’s Play Osu!）

代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

int n;

double p[NS], g[NS], h[NS], f[NS];

int main(int argc, char const* argv[])
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i += 1) scanf("%lf", &p[i]);
    for (int i = 1; i <= n; i += 1)
    {
        g[i] = p[i] * (g[i - 1] + 1);
        h[i] = p[i] * (h[i - 1] + 2 * g[i - 1] + 1);
        f[i] = p[i] * (f[i - 1] + 3 * h[i - 1] + 3 * g[i - 1] + 1)
            +(1 - p[i]) * f[i - 1];
    }
    printf("%.1f\n", f[n]);
    return 0;
}