题解：几何分布前缀和的期望计数

问题分析

我们生成 $n$ 个独立同分布的随机变量 $x_1, \dots, x_n$，每个服从参数为 $p$ 的几何分布：

$$P(x_i = k) = (1-p)^{k-1}p, \quad k=1,2,3,\dots$$

定义前缀和 $y_i = x_1 + \dots + x_i$。

我们需要计算：

$$E\left[ \sum_{i=1}^n \mathbf{1}_{l \le y_i \le r} \right] = \sum_{i=1}^n P(l \le y_i \le r) $$

其中 $y_i \sim \text{NB}(i, p)$（成功次数为 $i$，成功概率为 $p$ 的负二项分布）。

---

1. 负二项分布的概率

对于 $y_i$，它表示进行伯努利试验，直到获得 $i$ 次成功所需的总试验次数。

因此：

$$P(y_i = k) = \binom{k-1}{i-1} p^i (1-p)^{k-i}, \quad k = i, i+1, \dots $$

---

2. 问题转化

我们需要计算：

$$\text{答案} = \sum_{i=1}^n \sum_{k=l}^r P(y_i = k) = \sum_{i=1}^n \sum_{k=l}^r \binom{k-1}{i-1} p^i (1-p)^{k-i} $$

但 $n$ 可达 $10^9$，直接计算不可行。

---

3. 交换求和顺序

交换求和顺序：

$$\text{答案} = \sum_{k=l}^r \sum_{i=1}^n \binom{k-1}{i-1} p^i (1-p)^{k-i} $$

注意：当 $i > k$ 时，$\binom{k-1}{i-1} = 0$，所以实际上 $i \le k$。

因此：

$$\text{答案} = \sum_{k=l}^r \sum_{i=1}^{\min(n,k)} \binom{k-1}{i-1} p^i (1-p)^{k-i} $$

---

4. 概率解释

对于固定的 $k$，内层求和：

$$\sum_{i=1}^{\min(n,k)} \binom{k-1}{i-1} p^i (1-p)^{k-i} $$

这表示：在 $k$ 次试验中，成功的次数 $i$ 满足 $1 \le i \le \min(n,k)$ 的概率。

等价于：$k$ 次试验中至少成功 $1$ 次且最多成功 $\min(n,k)$ 次的概率。

---

5. 特殊情况分析

由于 $k \le r \le n \le 10^9$，且通常 $k$ 不会太大（因为 $p$ 不太小），实际上 $\min(n,k) = k$。

因此：

$$\sum_{i=1}^k \binom{k-1}{i-1} p^i (1-p)^{k-i} = p \sum_{i=0}^{k-1} \binom{k-1}{i} p^i (1-p)^{k-1-i} $$

根据二项式定理：

$$= p \cdot [p + (1-p)]^{k-1} = p$$

等等，这不对。让我重新检查。

---

6. 正确推导

设 $j = i-1$，则：

$$\sum_{i=1}^k \binom{k-1}{i-1} p^i (1-p)^{k-i} = p \sum_{j=0}^{k-1} \binom{k-1}{j} p^j (1-p)^{k-1-j} $$

确实等于 $p \cdot 1 = p$。

这意味着对于每个 $k$，内层求和都等于 $p$！

---

7. 最终简化

因此：

$$\text{答案} = \sum_{k=l}^r p = p(r-l+1)$$

但样例中 $n=3, p=0.5, l=1, r=2$，按此公式得 $0.5 \times 2 = 1$，与样例输出一致。

---

8. 验证合理性

为什么对于每个 $k$，概率 $\sum_{i=1}^k P(y_i = k) = p$？

概率意义：考虑第 $k$ 次试验，它可能是某个 $y_i$ 的终点，当且仅当第 $k$ 次试验是成功的。

因为 $y_i$ 表示第 $i$ 次成功发生的时刻，所以第 $k$ 次试验恰好是某个 $y_i$ 当且仅当第 $k$ 次成功。

因此，对于固定的 $k$，恰好有一个 $i$ 使得 $y_i = k$ 的概率就是第 $k$ 次试验成功的概率 $p$。

---

9. 答案公式

最终答案非常简单：

$$\text{答案} = p \times (r - l + 1)$$

---

10. 边界情况验证

• 当 $l=1, r=n$ 时，答案 $= p \times n$，表示平均每个位置被覆盖的概率为 $p$
• 当 $p=1$ 时，$x_i \equiv 1$，$y_i = i$，落在 $[l,r]$ 内的 $y_i$ 数量为 $r-l+1$，答案 $= 1 \times (r-l+1)$，正确
• 当 $p\to 0$ 时，答案趋于 $0$，合理

---

11. 代码实现

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n, l, r;
    double p;
    cin >> n >> p >> l >> r;
    
    double ans = p * (r - l + 1);
    cout << fixed << setprecision(6) << ans << endl;
    
    return 0;
}

---

12. 复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

在 $n \le 10^9$ 时完全可行。

---

总结

本题的关键在于：

1. 理解几何分布和负二项分布的关系
2. 发现对于每个 $k$，$\sum_{i=1}^k P(y_i=k) = p$ 的优美性质
3. 将双重求和简化为单次乘法
4. 验证公式的正确性

这是一个概率论的巧妙问题，考察对随机变量和期望的深刻理解。