考点：概率论

数据规模 n ≤ 1e6 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：k ≤ 1e6，n ≤ 1e6
• 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：概率论

用期望的线性性质拆解问题，避免枚举全部状态。

思路框架（概率论 通法 · 非本题专属）

1. 期望的线性性：E(X+Y) = E(X)+E(Y)，即使变量不独立也成立。
2. 把总期望拆成若干「指示变量」的期望之和，分别求每个事件发生的概率。
3. 按定义算期望时，用 Σ(取值 × 概率)。
4. 涉及无穷过程时，利用递推 / 马尔可夫性质列方程解。

实现要点：计数期望时，先算总方案数，再算目标方案数，比值即概率。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

• 误以为期望线性性需要独立性。
• 概率分母（总方案数）统计错。

对照本题

• 数据规模 n ≤ 1e6，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。

本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 1 1 → 输出 1.000000000

只有一杯水，第一回合就可以喝完。

样例 2：输入 2 1 → 输出 2.000000000

有50%的概率1回合喝完，有25%的概率需要2回合 ，有12.5%的概率需要3回合……

总期望为0.5*2+0.25*3+0.125*4+……=2

样例 3：输入 2 2 → 输出 4.000000000

第一回合有100%的概率喝一杯水。

第二回合无论是否选到有水的杯子都不会喝水。

0.5*3+0.25*4+0.125*5+...=4