CF618G Combining Slimes 题解

本文主要是介绍CF618G Combining Slimes 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CF618G Combining Slimes

首先考虑根据期望的线性性质对于每一个数分开来计算贡献，之后再求出每一个数出现的概率即可。

也不是很清楚这个东西是不是线性性质。

但是说实话就是对于所有数一起考虑是不能入手的。

之后我们发现事实上任意的数都有可能出现，发现其没有取模，我们不妨计算一下一个数可能出现的概率。

如果说这个数是 $x$ ，那么其概率是 $1 - 10^{-9})^{2^{x - 1}}$ 。算一下发现 $x = 50$ 的时候这个东西基本上都趋近于 $0$ 了。那么我们可以直接只考虑前面的 $50$ 个数。

我们考虑算每个数至少出现一次的概率，那么设其为 $a (i, j)$ 那么可以得到转移方程：
$\times a(i, j - 1)$

就是考虑前面出现的同时出现两个数的情况，那么肯定有一个拼成的数需要占用一个位置。

显然初值是 $a (1, 1) = p, a (1, 2) = 1 - p$ 。

但是发现 $n$ 实际上还是很大，我们不能将所有的值都求出来，根据上文的经验，我们发现当 $a (i, j)$ 其中 $i > 50$ 的时候也趋近于零，那么之后的所有值我们都可以用 $a (50, j)$ 进行代替。

之后我们计算转移的方程 $f (i, j)$ 表示考虑了最后的 $i$ 个格子，从右开始数第 $i$ 个格子恰好是 $j$ 后面的值的期望。

注意因为是恰好，我们之前计算的 $a$ 是至少，那么我们不妨设 $\times (1 - a(i - 1, j))$

这篇关于CF618G Combining Slimes 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！