题解 P6125 【[JSOI2009]有趣的游戏】

· · 题解

我也是百思不得其解后看了这篇博客后才明白了概率到期望的转化，但不幸的是这篇文章依然有一个小"迷"人的地方

首先问题可以被等价成在 AC 自动机上的一个匹配过程，匹配到一些关键点后会停止，求到这些关键点停下的概率

考虑设 f(i)=P(i点被经过)的设法存在两个问题

不妨转换设法

f(i)=E(i$点被经过次数$)

发现这样的话，每个点都具有定义，且在关键点时其到达次数的期望=在这里停止的概率(因为你只会到达这样的点一次)

这样就可以用全期望公式写每个点从其余点过来的转移过程了，设x\to y转移的概率是 P_{x\to y},容易注意到1=\sum_{y}P_{x\to y}

f_x=\begin{cases}1+\sum_{y }P_{y\to x}f_y&x=0\\\sum_{y }P_{y\to x}f_y&x\neq0\end{cases}

解释下那个1是状态初始累计的

然后高斯消元就不存在问题了

到这里你可能会有一点疑惑，关于初值 f_0 ，其实是不需要的且未知的，注意到我们列出的方程有n个，未知数也是n个，因此都是可以解出来的