← 返回题单
题单练习 概率与期望DP
← 上一题 下一题 →

A7126 | Let's Play Osu!

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

你在玩一个叫做 Osu 的游戏（某音游）！我们来简化一下游戏规则。一局游戏中需要点击 $n$ 次。每一次点击有两种结果：正确或失误。我们定义正确为符号 O，失误为 X，那么整局游戏可以被写成一个长度为 $n$ 的由字符 X 或 O 组成的字符串。

用这个字符串你可以用以下的方法计算游戏的得分：对于一个极大的连续的 O 连击，将连击的次数的平方加入到总得分中（即连续的 O 的个数的平方）。举例说明，如果你的游戏序列为 OOXOOOXXOO，那么极大连续的 O 连击共有三个：OO，OOO，OO，所以你的总得分为 $2^2 + 3^2 + 2^2= 17$ 。如果整局游戏里没有一次成功的点击那么总得分就为 $0$。

你现在知道了第 $i$ 次 ($1\leq i\leq n$)点击成功的概率为 $p_i$，换句话说，字符串中第 $i$ 个字符有 $p_i$ 的概率成为 O，有 $1-p_i$ 的概率成为 X，你的任务是算出你游戏总得分的期望值。

输入格式

第一行包含一个整数表示点击的次数 $n$ $( 1\leq n\leq 10^5 )$ 第二行包含 $n$ 个由空格间隔开的实数 $p_1,p_2,...,p_n ( 0\leq p_i\leq 1 )$ 输入的 $p_i$ 最多为六位小数。

输出格式

输出一个实数——你游戏的期望得分。你的答案必须与标准答案的误差不超过 $10^{-6}$

输入输出样例

输入 #1
3
0.5 0.5 0.5
输出 #1
2.750000000000000
输入 #2
4
0.7 0.2 0.1 0.9
输出 #2
2.489200000000000
输入 #3
5
1 1 1 1 1
输出 #3
25.000000000000000
C++ 编辑器
输入
输出