P4507 [CTSC2013]猴子大战 题解

· · 题解

猴子大战

如果设 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) 。