题目描述

TH14东方长明堂将于2012年9月1日发布。

本作的BOMB系统得到了更新。初始时,玩家有N个神灵。每使用一次BOMB,神灵数量就有可能发生变化。总结起来,使用一次BOMB,减少i个神灵的概率是p[i](0 <= i <= M)。一旦神灵数量小于M个,就不能使用BOMB。

现在你得到了东方长明堂的试玩版,求能使用BOMB的次数的期望值。

换句话说,如果不停地使用BOMB,平均情况下能使用几次。

时间限制:1s

内存限制:256MB

//样例解释

//有0.5的概率使用1次,0.25的概率使用2次,0.125的概率使用3次

//所以答案=0.5*1+0.25*2+0.125*3+….

//可以证明这个数列的和是2

对于30%:N <= 100000, p[0] = 0

对于另外20%:N <= 100000

对于另外30%:N <= 10^8, p[0] = 0

对于100%:N <= 10^8, M <= 5, 保证中间过程量答案可以用double类型正常存储

输入格式

第一行两个正整数N, M

接下来M+1个实数,表示p[i]

输出格式

一个实数,表示答案。保留1位小数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论