CF618G Combining Slimes

你的朋友最近送给你一些史莱姆作为生日礼物。你有大量价值为 $1$ 和 $2$ 的史莱姆，你决定用这些史莱姆发明一款游戏。 你用 $n$ 个空格初始化一排空位。你还选择一个数字 $p$ 供游戏中使用。然后，你会在最后一个空格还是空的时候，持续进行以下步骤： 1. 以概率 $\frac{p}{10^9}$ 选择一个价值为 $1$ 的史莱姆，以概率 $1-\frac{p}{10^9}$ 选择一个价值为 $2$ 的史莱姆。你将选中的史莱姆放在棋盘的最后一个空格上。 2. 你会尽量将该史莱姆向左推。如果它遇到另一个史莱姆，并且二者的数值都为 $v$，你会把这两个史莱姆合成为一个价值为 $v+1$ 的史莱姆。这个过程会一直持续，直到该史莱姆到达棋盘的左端，或者遇到一个与自身数值不同的史莱姆为止。 你已经玩了几次这个游戏，但现在有点腻了。你现在想知道，在游戏结束后，棋盘上所有史莱姆数值之和的期望是多少。

输入第一行包含两个整数 $n,p$，满足 $1\leq n \leq 10^{9}$，$1\leq p < 10^{9}$。

输出游戏结束后，棋盘上所有史莱姆数值之和的期望值。你的答案如果与标准答案的绝对或相对误差不超过 $10^{-4}$ 即视为正确。 具体来说，假设你的答案为 $a$，标准答案为 $b$。当且仅当 $|a-b|\leq 10^{-4}\max(1,|b|)$ 时，判题程序会认为你的答案正确。

在第一个样例中，棋盘有两个格子，每次有 $0.5$ 的概率出现 $1$，$0.5$ 的概率出现 $2$。 最终棋盘可能状态为 $1\,2$，概率为 $0.25$；$2\,1$，概率为 $0.375$；$3\,2$，概率为 $0.1875$；$3\,1$，概率为 $0.1875$。所以期望为 $(1+2)\cdot 0.25+(2+1)\cdot 0.375+(3+2)\cdot 0.1875+(3+1)\cdot 0.1875=3.5625$。 由 ChatGPT 5 翻译