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

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

[SDOI2017] 硬币游戏

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

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

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

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

$$\begin{array}{}\text{(1)}& >\begin{array}{r}>F_i(x)=\sum _{k=0}{f}_{i,k}\cdot x^k>\end{array}>\end{array}$$

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

$$\begin{array}{}\text{(2)}& >\begin{array}{r}>g_k=g_{k+1}+\sum _{i=1}^n{f}_{i,k}>\end{array}>\end{array}$$

根据概率生成函数性质有 $\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{array}{}\text{(3)}& >\begin{array}{r}>g_{k-len}\cdot (\frac{1}{2}{)}^m>\end{array}>\end{array}$$

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

$$\begin{array}{}\text{(4)}& >\begin{array}{r}>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{array}>\end{array}$$

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

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