QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[+5]

# 7962. 前缀和

Statistics

题目描述

小兰很喜欢随机数。

TA 首先选定了一个实数 0<p<1,然后生成了 n 个随机数 x1,,xn,每个数是独立按照如下方式生成的:

  • xip 的概率是 1,有 (1p)p 的概率是 2,有 (1p)2p 的概率是 3,以此类推。

生成完这些随机数之后,小艾对这个数列求了前缀和,得到了数列 y1,,yn

给定 1lrn,小兰想知道,期望有多少 yi 落在 [l,r] 内?

输入格式

从标准输入读入数据。

一行输入四个数 n,p,l,r。保证 1lrn109p 的位数不超过 6

输出格式

输出到标准输出。

输出一个实数,表示答案。你需要保证答案的绝对或相对误差不超过 106

样例1输入

3 0.5 1 2

样例1输出

1.000000

样例1解释

1/4 的概率,x1=1x2>1,此时只有 y1 落在 [1,2] 内。

1/4 的概率,x1=1x2=1,此时 y1,y2 落在 [1,2] 内。

1/4 的概率,x1=2,此时只有 y1 落在 [1,2] 内。

所以期望是 1/4(1+2+1)=1