「Summary」2023-08-06 做题记录

我怎么又不带笔到机房？？？

[SDOI2017] 硬币游戏

我做过歌唱王国这题，然后一眼觉得就是这个，第二眼就把思路丢了，想了一个对正解毫无帮助的暴力。🤣

现在我要开始推🦁了！！！1

哈哈哈哈哈哈哈哈哈哈哈哈哈。
以下引用部分内容为草稿

设 $f_{i, k}$ 表示第 $i$ 个人在第 $k$ 轮抛完之后获胜的概率，把这个概率生> 成函数写出来。

$$ > \begin{aligned} > F_i(x) = \sum_{k= 0} f_{i, k} \cdot x^k > \end{aligned} > $$

然后延续歌唱王国的思路，设 $g_{k}$ 表示在 $k$ 轮之后都还没有人获胜的概率，> 于是可以知道 $\sum_{k = 0} g_k = 1$，写一下转移关系

$$ > \begin{aligned} > g_k = g_{k + 1} + \sum_{i = 1}^{n} f_{i, k} > \end{aligned} > $$

根据概率生成函数性质有 $\sum_{i = 1}^{n}F_i(1) = 1$。

然后为了计算每个人获胜的概率，我们钦定在第 $k$ 轮后连续抛出的就是第 $t$ 个人> 的串，那么在 $k + t$ 轮第 $t$ 个人获胜的概率是 $g_k \times (\frac{1}> {2})^{m}$，但是这样有点小问题，因为这个游戏可能会提前结束。
我来🤔一下，假设是 $t$ 和 $s$ 撞了，$s$ 使游戏提前结束，假设 $len$ 这一部> 分 $t$ 和 $s$ 重合，那么提前结束的概率就是

$$ > \begin{aligned} > g_{k - len} \cdot {(\frac{1}{2})^m} > \end{aligned} > $$

并且我要保证在这之前不会继续撞，写完整是。

$$ > \begin{aligned} > f_{t,k+m} = g_{k}\times (\frac{1}{2})^m - \sum_{i = 1}^{n} > \sum_{j = 1}^{m} [S_{t}[1, j] = S_{i}[m - j + 1, m]] f_{i, k > + j} \times (\frac{1}{2})^{m - j} > \end{aligned} > $$

写成生成函数的形式，然后我发现我搞错了。

乐，我现在懂了，放在这里，我看看我明天能不能想起来我是犯了什么小丑错误。