题意描述

$\text{OSU}$ 是一款群众喜闻乐见的休闲软件。

我们可以把$\text{OSU}$的规则简化与改编成以下的样子:

一共有$n$次操作，每次操作只有成功与失败之分。

成功对应$1$，失败对应$0$，$n$次操作对应为$1$个长度为$n$的$01$串。

在这个串中连续的$x$个 $1$ 可以贡献 $x^3$的分数，这$x$个$1$不能被其他连续的$1$所包含（也就是极长的一串$1$，具体见样例解释）

现在给出$n$，以及每个操作的成功率，请你输出期望分数。

输入格式

第一行有一个正整数$n$,表示操作个数。

接下来$n$行每行有一个实数$p_i$，表示每个操作的成功率。

输出格式

输出仅有一行，包含一个实数，表示答案。

输出时，请保留一位小数。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

6.0

样例解释

得分序列共有以下几种可能：

000分数为$0$
001分数为$1$
010分数为$1$
100分数为$1$
101分数为$2$
110分数为$8$
011分数为$8$
111分数为$27$

以上得分最后的总和为$48$，则其期望得分为$\frac{48}{8} = 6.0$

数据范围和约定

对于$100\%$的数据，保证$0 \leq N \leq 10^5$，$0 \leq p_i \leq 1$

分析

简单的期望$\text{dp}$入门题目。

设$E(x_i)$表示前$i$个位置的期望得分，$E(l1_i)$表示打到第$i$个点的期望长度，$E(l2_i)$表示打到第$i$个点的期望长度的平方。

考虑单个位置对于答案的贡献。设之前的长度为$x$，若打中，则长度变为$x + 1$，对得分的贡献就是$(x + 1)^3 - x^3 = 3x^2 + 3x + 1$

综上，可得状态转移方程

$E(x_i) = E(x_{i - 1}) + p_i(3 \times E(l2_{i - 1}) + 3 \times E(l1_{i - 1}) + 1)$

考虑如何维护$E(l1_i)$ 与 $E(l2_i)$ 。显然，

$E(l1_i) = p_i(E(l1_{i - 1}) + 1)$

对于$E(l2_i)$，则考虑当前位置是否打中，设之前长度为$x$，若打中，则有$(x + 1)^2 - x^2 = 2x + 1$。

将其带到 $E(l2_i)$ 中，则有

$E(l2_i) = p_i(E(l2_{i - 1}) + 2 \times E(l1_{i - 1}) + 1)$

剩下的见代码即可。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

int n;
long double f[N] , len1[N] , len2[N] , p1;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> p1;
        f[i] = f[i - 1] + p1 * (3 * len2[i - 1] + 3 * len1[i - 1] + 1);
        len1[i] = p1 * (len1[i - 1] + 1);
        len2[i] = p1 * (len2[i - 1] + 2 * len1[i - 1] + 1);
    }
    cout << fixed << setprecision(1) << f[n] << "\n";
    return 0;
}