时间限制： 1.0 秒

空间限制： 512 MiB

题目描述

小兰很喜欢随机数。 TA 首先选定了一个实数 0<p<1，然后生成了 n 个随机数 x1,…,xn，每个数是独立按照如下方式生成的：

x i有 p 的概率是 1有 (1−p)p 的概率是 2，有 (1−p) ^2*p 的概率是 3 以此类推。

生成完这些随机数之后，小艾对这个数列求了前缀和，得到了数列 y 1,…,y n 。

给定 1≤l≤r≤n，小兰想知道，期望有多少 y i落在 [l,r] 内？

输入格式

从标准输入读入数据。

一行输入四个数

n,p,l,r。保证

1≤l≤r≤n≤10 ^9,

p 的位数不超过 6。

输出格式

输出到标准输出。

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

样例1输入

3 0.5 1 2

样例1输出

1.000000

我的代码

#include<bits/stdc++.h>
using namespace std;
double pre(int n,double p,int l,int r) {
    vector<double>dp(n+1,0.0);
    vector<double>cum(n+1,0.0);
    dp[1]=p;
    cum[1]=p;
    for (int i=2;i<n;i++) {
        dp[i]=(1-p)*dp[i-1];
        cum[i]=cum[i-1]+dp[i];
    }
    double ex=cum[r]-cum[l-1];
    if(l>1)ex+=cum[l-1];
    return ex;
}
int main(){
    int n, l, r;
    double p;
    cin>>n>>p>>l>>r;
    double result = pre(n, p, l, r);
    cout.setf(ios::fixed);
    cout.precision(6);
    cout<<result;
    return 0;
}

我的思路

首先，我们可以通过动态规划的方法计算每个前缀和的概率，并将其保存在一个数组中。设 dp[i] 表示前缀和为 i 的概率。

对于第一个随机数，有 dp[1] = p、dp[2] = (1-p)p、dp[3] = (1-p)^2p，以此类推。

然后，我们可以计算累积概率数组 cumProb[i]，表示前缀和小于等于 i 的概率。

累积概率数组的计算公式为 cumProb[i] = cumProb[i-1] + dp[i]。

接下来，我们可以通过 cumProb 数组计算指定区间 [l, r] 的前缀和的期望。

期望的计算公式为 E = cumProb[r] - cumProb[l-1]。

最后，将得到的期望输出即可。