题目描述
小兰很喜欢随机数。
TA 首先选定了一个实数 0<p<1,然后生成了 n 个随机数 x1,…,xn,每个数是独立按照如下方式生成的:
- xi 有 p 的概率是 1,有 (1−p)p 的概率是 2,有 (1−p)2p 的概率是 3,以此类推。
生成完这些随机数之后,小艾对这个数列求了前缀和,得到了数列 y1,…,yn。
给定 1≤l≤r≤n,小兰想知道,期望有多少 yi 落在 [l,r] 内?
输入格式
从标准输入读入数据。
一行输入四个数 n,p,l,r。保证 1≤l≤r≤n≤109,p 的位数不超过 6。
输出格式
输出到标准输出。
输出一个实数,表示答案。你需要保证答案的绝对或相对误差不超过 10−6。
样例1输入
3 0.5 1 2
样例1输出
1.000000
样例1解释
有 1/4 的概率,x1=1 而 x2>1,此时只有 y1 落在 [1,2] 内。
有 1/4 的概率,x1=1 且 x2=1,此时 y1,y2 落在 [1,2] 内。
有 1/4 的概率,x1=2,此时只有 y1 落在 [1,2] 内。
所以期望是 1/4⋅(1+2+1)=1。