#P6269. 「THUPC 2024 初赛」前缀和

    ID: 5559 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-几何分布指示变量期望线性性

「THUPC 2024 初赛」前缀和

题目描述

小兰很喜欢随机数。

TA 首先选定了一个实数 0<p<10 < p < 1,然后生成了 nn 个随机数 x1,…,xnx_1,\dots,x_n,每个数是独立按照如下方式生成的:

  • xix_i 有 pp 的概率是 11,有 (1−p)p(1-p)p 的概率是 22,有 (1−p)2p(1-p)^2p 的概率是 33,以此类推。

生成完这些随机数之后,小艾对这个数列求了前缀和,得到了数列 y1,…,yny_1,\dots,y_n。

给定 1≤l≤r≤n1\leq l\leq r\leq n,小兰想知道,期望有多少 yiy_i 落在 [l,r][l, r] 内?

输入格式

一行输入四个数 n,p,l,rn, p, l, r。保证 1≤l≤r≤n≤1091\leq l\leq r\leq n\leq 10^9,pp 的位数不超过 66。

输出格式

输出一个实数,表示答案。你需要保证答案的绝对或相对误差不超过 10−610^{-6}。

3 0.5 1 2

1.000000

题目使用协议

来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库(https://github.com/ckw20/thupc2024_pre_public)

  1. 任何单位或个人都可以免费使用或转载本仓库的题目;

  2. 任何单位或个人在使用本仓库题目时,应做到无偿、公开,严禁使用这些题目盈利或给这些题目添加特殊权限;

  3. 如果条件允许,请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法;否则,请附上本仓库的 github 地址。