自动搬运

查看原文

来自洛谷，原作者为

	zzw4257 于浩歌狂热之际中寒；于天上看见深渊。于一切眼中看见无所有；于无所希望中得救。

搬运于2025-08-24 22:17:41，当前版本为作者最后更新于2020-12-26 15:14:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

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

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

• $f(x)(x|$ $x$不是关键点 $)$
• $f($ 根 $)$的取值未定，轻易的可以发现，$f($ 根 $)=1$明显与这个匹配过程可以反复返根矛盾

不妨转换设法

$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$个，因此都是可以解出来的