Problem Description

Xiaolan really likes random numbers.

They first choose a real number $0 < p < 1$, and then generate $n$ random numbers $x_1,\dots,x_n$. Each number is generated independently in the following way:

• $x_i$ equals $1$ with probability $p$, equals $2$ with probability $(1-p)p$, equals $3$ with probability $(1-p)^2p$, and so on.

After generating these random numbers, Xiaoai computes the prefix sums of this sequence and obtains a sequence $y_1,\dots,y_n$.

Given $1\leq l\leq r\leq n$, Xiaolan wants to know: in expectation, how many $y_i$ fall within $[l, r]$?

Input Format

One line contains four numbers $n, p, l, r$. It is guaranteed that $1\leq l\leq r\leq n\leq 10^9$, and $p$ has at most $6$ digits.

Output Format

Output a real number, the answer. You need to ensure that the absolute or relative error does not exceed $10^{-6}$.

3 0.5 1 2

1.000000

Hint

Sample #1 Explanation

With probability $1/4$, $x_1=1$ and $x_2>1$. In this case, only $y_1$ falls within $[1, 2]$.

With probability $1/4$, $x_1=1$ and $x_2=1$. In this case, $y_1,y_2$ fall within $[1, 2]$.

With probability $1/4$, $x_1=2$. In this case, only $y_1$ falls within $[1, 2]$.

So the expectation is $1/4\cdot (1 + 2 + 1) = 1$.

Problem License

From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational) Preliminary.

The following “this repository” all refer to the official THUPC2024 Preliminary repository (https://github.com/ckw20/thupc2024_pre_public)

1. Any organization or individual may use or repost the problems in this repository free of charge.

2. When using the problems in this repository, any organization or individual should do so for free and publicly. It is strictly forbidden to profit from these problems or add special access restrictions to them.

3. If possible, please also provide ways to obtain resources such as testdata, standard solutions, and editorials when using the problems in this repository; otherwise, please attach the GitHub link of this repository.

Translated by ChatGPT 5