自动搬运

查看原文

来自洛谷，原作者为

	uniqueharry I wanna achieve something big

搬运于2025-08-24 22:00:51，当前版本为作者最后更新于2021-12-15 13:10:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

猴子大战

如果设 $f_S$ 表示手中卡牌状态为 $S$ 时的胜率，有：

$f_S= \sum\limits_{i\in S}\sum\limits_{j\in \overline{S}}p_{i,j}\times f_{S \cup \{j\}} + (1-p_{i,j})\times f_{S \setminus \{i\}}$

是一个有环的 dp，如果暴力高斯消元，复杂度是 $O((2^n)^3)$ 的，不能接受。

可以发现一个结论：$f_A + f_B = f_{A \cup B}$ 。

证明如下：

假如是三个人 $A,B,C$ 在玩这个游戏，那么肯定有 $f_A + f_B + f_C = 1$ ，因为最后一定有一个人会取胜。

而对于 $A$ 而言，要么是赢要么是输，则 $f_A + f_{B \cup C} = 1$，则 $f_B + f_C = f_{B \cup C}$ 。

有这个结论之后可以把给出的每个 01 串为 1 的位置的答案累加起来即可。

至于计算 $f_i$ ，模仿刚才的做法，可以对于 $i$ 列出：

$f_i = \sum\limits_{j \neq i} \frac{p_{i,j}\times (f_i + f_j) + (1-p_{i,j})\times 0}{n-1}$

上面的 $f_i + f_j$ 即为 $f_{\{i \} \cup \{j\}}$,$0$ 即为 $f_{\{i\} \setminus \{i\}}$

而这 $n$ 个方程右边都没有常数，所以有 $n - 1$ 个方程和另外一个方程本质相同，但是就像我们刚才推导结论时所说的，一定有一个人会取胜，所以 $\sum\limits f_i = 1$ ，现在 $n$ 个方程 ， $n$ 个未知数，高斯消元即可。 时间复杂度 $O(n^3)$ 。