题解 P4321 【随机漫游】

· · 题解

很有意思的一道题目。

用f(x,S)表示从x出发，已经走过了点集S,走遍全图的期望。

这一类期望题可以考虑高斯消元，构造方程如下：

f(x,S) = \frac{1}{du(x)} (f(y,S) \times [ y \in S ]+ f(y,S \cup j ) \times [ y \not\in S ]; )

直接进行高斯消元的话，复杂度肯定受不了，考虑一下该方程的特殊性质。

由于每次走一个新的点，已经走过的点集只可能扩大不可能缩小，所以我们可以利用这个性质进行分层，每次对于一个S进行高斯消元，求出一些信息后，利用这些信息，继续进行下一层的高斯消元。这样每次高斯消元时，复杂度大大降低。

复杂度O(n^32^n+Q)