P9963 [THUPC 2024 初赛] 前缀和 题解

· · 题解

对于此题的式子，有一个非常有趣的想法：

考虑有一排灯，其中每个灯都有 p 的概率点亮。

然后我们惊喜地发现，两个点亮灯之间的距离正好就是题目中说的 x_i。

然后我们又惊喜地发现，点亮的第i盏灯的位置正好就是 x_i 的前缀和。因为 l,r\le n，我们甚至不需要考虑 [l,r] 之间没有灯被点亮的情况。

于是对于每盏灯，都有 p 的概率对答案造成 1 的贡献，所以答案就是 (r-l+1)p。

#include<iostream>
#include<cstdio>
using namespace std;
double n,p,l,r;
signed main()
{
    scanf("%lf%lf%lf%lf",&n,&p,&l,&r);
    printf("%0.7lf",(r-l+1)*p);
}