题解 CF113D 【Museum】

shao0320 · 2021-01-04 17:29:37 · 题解

题意简述：

给定一个无向图，从a节点和b节点开始随机游走，走到每个点时有两种可能，在第i个点有p_i的可能停下，或者随机找一条出边出去，两个点走到同一个点时停止。

分析：

听说正解是高斯消元，这里给出一种玄学做法。

由于时间满足单调性，因此容易想到一种dp。

设f(i,x,y)表示，第i轮游走，第1个人停在了x号节点，第2个人停在了y号节点的概率。

转移很简单，有四种情况，第一个人走/不走、第二个人走/不走。

时间复杂度为O(TN^4)，其中T表示游走次数。

问题就是这个T该取多少。

首先，肯定是T取的越大，结果越精确，注意到有10^{-6}的可接受误差，因此可以考虑取一个常数。

但常数过大这样会TLE，注意到如果当前状态的概率过小，也就不会对后续状态产生非常大的影响了，因此可以设一个eps值，当当前状态概率\leq eps时就不计算这个状态的贡献了。

经过作者多次调参，发现T=150000,eps=1e^{-30}时可以通过。