从 ACAM 随机游走 到 概率期望转移 再到 高斯消元主元法 最后更新于 2025-05-01 20:41:23

题目： [P6125 [JSOI2009] 有趣的游戏](https://www.luogu.com.cn/problem/P6125) [P4077 [SDOI2016] 硬币游戏](https://www.luogu.com.cn/problem/P4077) [CF gym 103119 B Boring Problem](https://codeforces.com/gym/103119/problem/B) ## 学习笔记：ACAM 随机游走 ### 正推和倒推 分为概率 DP 和期望 DP 两种。 [有趣的游戏](https://www.luogu.com.cn/problem/P6125) 这道题目用的是概率 DP，另一道用的是期望 DP。 首先理解什么是 **正推** ，什么是 **倒推** ： - **正推** 是当前点用所有 **前驱** 结点的信息表示 - **倒推** 是当前点用所有 **后继** 节点的信息表示 倒推： $$ f_i(u)=\sum_{c\in\Sigma} f_i(\delta(u,c)) \cdot p_c $$ 正推： $$ g(y)=\sum_{x\notin Key \land \delta(x,c)=y} g(x) \cdot p_c $$ 然后考虑正推和倒推的适用范围： 一般有求概率是正推，求期望是逆推。本质上是因为求期望如果正着推，还要记录一个到当前点的概率。具体见 [here](https://www.zhihu.com/question/464263211)。J 总结得 **终点状态唯一（可以被确定）** 用倒推，**终点状态不唯一（不可以被确定）** 用正推。 在题目中，常常有多种解法。设计一个状态判断是正推还是倒推，考虑： - 判断终止状态在该判断条件下，是否可以被确定。能被确定的用倒推，不能被确定的用正推。 - 判断后继状态是否能完全表示当前状态。可以则为倒推，否则为正推。 所以碰到一道概率期望 DP 的题目，有如下解决策略： 1. 设计状态。 2. 判断状态的初始位置（可以被确定的位置）在起点还是在终点。 3. 列出转移式。 回到 ACAM 随机游走。 ### 概率 DP 首先自然会想到的是 设以每个点结束的概率。但是发现非关键点的概率显然为 $0$，不太能转移。考虑非关键点如何才能有值： - 要么记录一个系数序列，表示当前点到所有关键点的概率 - 要么分开考虑每一个关键点，记录每一个点到该关键点的概率 上述两种情况本质相同。注意到第一种情况各关键点转移 **互相独立**，统一规约成第二种情况。 考虑关键点 $i$，当前点 $u$。设 $f_i(u)$ 为从 $u$ 开始到 $i$ 的概率。**关键点代表的是终止状态**，所以考虑倒推，则有： $$ f_i(u)= \begin{cases} 1 & u=i\\ 0 & u\ne i \land u\in \text{Key}\\ \sum_{c\in \Sigma} f_i(\delta(u,c))\cdot p_c & \text{otherwise.} \end{cases} $$ 即该点由所有后继决定。 上述式子加上高斯消元，ACAM 节点个数为 $O(nm)$，则时间复杂度为 $O((nm)^3\cdot n)$。 ### 期望 DP 这道题能用期望 DP 吗？~~总不能设还有多少步终止节点吧。~~ 思考终止点是该关键点的概率和什么相关。**注意到关键点只会出现一次**，设每个点的 **期望出现次数** 为 $g(u)$。 当 $u\in \text{Key}$ 时有 $g(u)=f_u(0)$。 出现次数与前驱点还是后继点有关：都有关，但是从后继点转移到该点需要知道 **所有该后继点的前驱点到该后继点的概率** 中该点占的比例。就是得先算每个点从起始点到达的概率。如果从前驱点来，就可以直接用概率乘上期望。 即有： $$ g(y)=\sum_{x\notin Key \land \delta(x,c)=y} g(x) \cdot p_c $$ 把 $x$ 做一个分类。分为 Trie 树边和 跳 Fail 边的。Trie 边的 $x$ 一定是 Trie 上的 $fa_y$。跳 Fail 边的要么深度大于等于自己的。所以便可以把用 $y$ 和其他点的信息表示 $fa_y$。 本题中 $p_c$ 恒等于 $\frac 1 2$，即有： $$ g(fa_y)=2\cdot g(y)-\sum_{x\notin Key \land \delta(x,c)=y\land x\ne fa_y} g(x) $$ 注意到每个点都可被儿子表示，故对于每个点的 $k$ 个儿子可以建立 $k-1$ 个方程。一共有 $n-1$ 个方程。 又有： $$ \sum_{u\in \text{Key}} g(u)=1 $$ 故 $n$ 个方程，$n$ 个未知数可解。 具体实现：每个点的 $g$ 表示成多个关键点的 $g$ 的系数序列，进行系数转移即可。 时间复杂度：$O(n^2m+n^3)$。 #### 实现注意事项： - 如何卡空间：逆 BFS 序每一层只有 $O(n)$ 个点，每次转移时只与当前层和上下一层有关，所以维护一个动态数组记录当前要用的信息，**要用时找到空缺的位置放上去，弃用时打个标记即可**。本题在第一次 Fail 更新或枚举到该点时更新，在父亲点被更新完后弃用。时间复杂度为 $O(n^2)$。 ### 为什么相同节点之间更新不会影响答案？ - 代码层面上，相同层更新只会是用自己的权值更新其 $ms$ 数组（即相减的数组），而 $ms$ 数组更新只会在上一层 $fa$ 时被用到。 - 含义上，每个点权值是由儿子贡献的，而更新只在大于等于自己深度的点，所以不会出现更新错误/循环更新的问题。 ## 主元法优化 ACAM 随机游走 [CF gym 103119 B Boring Problem](https://codeforces.com/gym/103119/problem/B) 在 [P4077 [SDOI2016] 硬币游戏](https://www.luogu.com.cn/problem/P4077) 中，我们已经使用过主元法了。当时是将所有叶子节点设为主元来转移。得到方程是在两两 LCA 上。 在本题中，题目求的是：从该点随机游走的期望路径长度。设为 $f$，显然有： $$ f(u)= \begin{cases} 0 & u\in\text{Key}\\ 1+\sum_{c} f(\delta(u,c)) \cdot p_c & \text{otherwise}. \end{cases} $$ 写成 $fa$ 的形式： $$ f(fa_u)=1+\sum_cf(\delta(fa_u,c))\cdot p_c $$ 右边有三种点：$u$ 自己，$u$ 的兄弟，比 $fa$ 深度小的若干个点。 便可以用 $u$ 的兄弟和比 $fa$ 深度小的若干个点来表示 $u$。假设我们深度从小到大遍历结点，比 $fa$ 深度小的若干个点可以被表示。 通过主元的思想，我们在每个儿子数量大于 $1$ 的结点，把它的儿子数量 $sz$ 的 $sz-1$ 个结点记作主元，唯一的那个儿子用其他儿子的系数序列表示。 特别地，根节点也算主元。 **注意到**，这样做的主元刚好 $n$ 个的。证明考虑增量法。 最后在所有叶子结点算贡献即可。 时间复杂度： - 转移： $O(n^2mk)$ - 高斯消元： $O(n^3)$ 总结：**主元法** 是用图上 **一部分结点** 当作 **未知量**，表示其他结点，最后在特定结点找到 **恒等式**，从而解除方程的方法。