AT_abc126_c [ABC126C] Dice and Coin

题目描述

すぬけ君有一个 $N$ 面的骰子，每个面上的数字为 $1$ 到 $N$，每个数字出现的概率相等，还有一枚正反面概率相等的硬币。すぬけ君将用这个骰子和硬币进行如下游戏：

1. 首先掷一次骰子，掷出的点数作为当前得分。
2. 只要得分在 $1$ 到 $K-1$ 之间，すぬけ君就不断掷硬币。如果掷出正面，则得分变为原来的 $2$ 倍；如果掷出反面，则得分变为 $0$。
3. 一旦得分变为 $0$ 或者达到 $K$ 及以上，游戏结束。如果得分达到 $K$ 及以上，则すぬけ君获胜；如果得分为 $0$，则すぬけ君失败。

给定 $N$ 和 $K$，请计算すぬけ君获胜的概率。

输入格式

输入为一行，包含两个整数：

$N$ $K$

输出格式

输出すぬけ君获胜的概率。若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例 1

输入

3 10

输出

0.145833333333

样例 2

输入

100000 5

输出

0.999973749998

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• 输入均为整数

样例解释 1

• 当骰子掷出 $1$ 时，要使得分达到 $10$ 及以上，需要连续掷 $4$ 次硬币且每次都是正面。概率为 $\frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}$。
• 当骰子掷出 $2$ 时，要使得分达到 $10$ 及以上，需要连续掷 $3$ 次硬币且每次都是正面。概率为 $\frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}$。
• 当骰子掷出 $3$ 时，要使得分达到 $10$ 及以上，需要连续掷 $2$ 次硬币且每次都是正面。概率为 $\frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}$。

因此，すぬけ君获胜的概率为 $\frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333$。

由 ChatGPT 4.1 翻译