期望 dp 的转移_杂项

期望 dp 的转移

我们通常会对一个过程进行期望 dp，此时就必定会涉及到期望的定义问题：

• 到达每个状态的概率本就有别，只有初状态和终状态的概率是 $1$，那此时对状态的“期望”如何定义？

按正常的理解思路，期望中蕴含着概率，是概率的积分，自然概率为 $p$ 的状态即使所有情况的价值都是 $1$，那其期望价值也是 $p$。

所以，在正向 $\rm dp$ 的时候，每当我们要把该情况的期望 $+1$，我们实际要做的是加上转移到该状态的概率，故我们需要同时维护期望和概率。

但初学 OI 时我们总是听过“期望要倒着转移”这种劝诫，在实操中我们发现倒着转移仅需维护期望，期望 $+1$ 是真的 $+1$，因为此时期望的定义基于“从此状态开始到终状态”的条件概率，前面的概率等转移到前面再乘上。

为什么从前往后转移时无法类似这样定义呢？因为状态需要蕴含过去的信息，所以初状态的概率是一定要伴随下来的，所以此时基于的条件概率就不像倒着转移性质那么优秀了。

随机游走模型

一个有向图，给定起点，若干个终点，走到任意一个终点就停下，否则以边权的概率往外走，问停在每个终点的概率。

将状态设为期望经过次数即可。

多串匹配问题 P3706 [SDOI2017] 硬币游戏

可以把朴素高消的 $(\sum s_i)^3\to n^3+n\sum s$。

$n$ 个串构成的 AC 自动机上的高斯消元（每个点从入边转移而来），可以化成 $n$ 个变量的主元式。

AC 自动机用的是按照 bfs 反序推，枚举到一个点的时候它的和式中除了父亲，其他点都确定了，可以直接推导出父亲的主元式。

单串匹配问题 字符集很大

这里的字符集很大是抽象版本的，题目可以给出若干规则，例如 $[1,10^8]$ 以内的字符出现概率是 $p$，$[10^8+1,10^9]$ 字符出现概率是 $q$，当然能压缩的边我们会压缩到 $\rm others$，但直接跑上面的算法仍然至少 $\cal O(n^2)$，我们可以进一步优化到不带 $\Sigma$。

kmp 也可以推导每个点从出边转移而来的式子，从前往后推，因为推到 $[1,i]$ 的时候，前面的都确定了，所以我们可以利用 $i$ 的和式推导出 $i+1$ 的一次函数。

你发现 kmp 很特殊，$i$ 的式子和 $fa_i$ 的式子只有 $s_{i+1}$ 的位置不同，所以我们用 $f_{fa_i}$ 的式子先减掉 $w_{fa_i,s_{fa_i+1}}f_{fa_i+1}$，再加上 $w_{i,{s_{i+1}}}f_{i+1}$，就是 $i$ 的式子。