F - Bomb Game 2
2huk
·
·
题解
F - Bomb Game 2
Description
有 n 个人排成一排。你需要进行若干次操作，直到只剩下一个人：
- 有 \dfrac 12 的概率，将第一个人刀了；
- 有 \dfrac 12 的概率，把第一个人挪到最后，其余人的位置向前移。
对于每个 1 \le i \le n，求出第 i 个人最终活下来的概率。
Solution
设 f_{i, j} 表示如果总共有 i 个人，第 j 个人最后活下来的概率。那么转移显然：
f_{i, j} = \left\{\begin{matrix} \dfrac 12 f_{i, i} & (j = 1)\\\dfrac 12(f_{i, j - 1} + f_{i - 1, j - 1}) & (j \ne 1)\end{matrix}\right.
那么第 i 个人最终活下来的概率即为 f_{n, i}。
发现转移是有环的。因此考虑解决这个问题。我们可以把 f_{i, 1} 拆开：
\begin{aligned} f_{i, 1} &= \dfrac 12 f_{i, i} \\ &= \dfrac 12 \cdot\dfrac 12(f_{i, i - 1} + f_{i - 1, i - 1}) \\ &= \dfrac 12 \cdot\dfrac 12\left[\dfrac 12(f_{i, i - 2} + f_{i - 1, i - 2}) + f_{i - 1, i - 1}\right] \\ &= \dfrac 12 \cdot\dfrac 12 \left\{ \dfrac 12 \left[ \dfrac 12 (f_{i, i - 3} + f_{i - 1, i - 3}) + f_{i - 1, i - 2}\right] + f_{i - 1, i - 1} \right\} \\ &= \dots \end{aligned}
这样就可以得到一个一元一次方程。即：
2^{-i}f_{i, 1} + \sum_{j = 1}^{i - 1} 2^{j - i - 1}f_{i - 1, j} = f_{i, 1}
移项可得：
f_{i, 1} = \dfrac {\sum_{j = 1}^{i - 1} 2^{j - i - 1}f_{i - 1, j}}{2^{-i} - 1}
然后就无环了，直接转移即可。
Code
https://www.luogu.com.cn/paste/rvrlflnu。