算法竞赛2026年8月13日约 13 分钟

随机游走

是先确定“状态”，再判断状态转移有没有环。绝大多数题最终会落到：概率 DP、期望 DP、线性方程组或马尔可夫链。

生成式文章封面

开始阅读

是先确定“状态”，再判断状态转移有没有环。绝大多数题最终会落到：概率 DP、期望 DP、线性方程组或马尔可夫链。

1. 先分清题目求什么

常见目标包括：

到达某个终点的概率
到达终点的期望步数
某个点被访问的概率或期望次数
最终停在各个终点的概率
第一次到达、恰好第 $k$ 步到达
多个棋子或多个随机变量同时运动

不同目标对应不同的状态值：

P(s)=\text{从状态 }s\text{ 出发成功的概率}

E(s)=\text{从状态 }s\text{ 出发到终止的期望步数}

2. 最基础的转移方程

假设状态 $s$ 可以转移到 $t$ ，概率为 $p(s,t)$ 。

到达目标的概率

P(s)=\sum_t p(s,t)P(t)

边界一般是：

P(\text{成功终点})=1,\qquad P(\text{失败终点})=0

到达终点的期望步数

因为当前转移本身消耗一步：

E(s)=1+\sum_t p(s,t)E(t)

终点满足：

E(\text{终点})=0

更一般地，如果从 $s$ 转移到 $t$ 的代价为 $c(s,t)$ ：

E(s)=\sum_t p(s,t)\bigl(c(s,t)+E(t)\bigr)

最容易犯的错误就是期望转移中漏掉当前这一步的代价。

3. 判断有没有环

这是选择算法的关键。

情况一：状态转移无环

例如：

每次位置只会增大
剩余血量只会减少
已收集物品数量只会增加
时间维度不断增加

这时直接使用 DP，按照拓扑序或逆序计算即可。

例如掷骰子向前走：

E[i]=1+\frac{1}{6}\sum_{d=1}^{6}E[i+d]

因为只依赖更大的位置，所以从终点向前倒推。

复杂度通常是：

O(\text{状态数}\times\text{转移数})

情况二：有环，但方程可以局部整理

例如在位置 $i$ 有概率 $p$ 原地不动：

E[i]=1+pE[i]+\sum_j p_jE[j]

把自身项移到左边：

E[i]=\frac{1+\sum_j p_jE[j]}{1-p}

因此，看到“可能原地不动”时不要直接死循环，而要把自环项移项。

类似地，如果：

P[i]=pP[i]+\sum_j p_jP[j]

那么：

P[i]=\frac{\sum_j p_jP[j]}{1-p}

情况三：一般有环

如果多个状态相互依赖：

E_1=1+\frac12E_2+\frac12E_3

E_2=1+\frac13E_1+\frac23E_3

就不能普通 DP，需要建立线性方程组。

对每个非终止状态 $i$ ：

E_i-\sum_j p_{ij}E_j=1

写成矩阵形式：

(I-P)E=\mathbf 1

然后使用高斯消元。

如果有 $n$ 个状态，普通高斯消元复杂度是：

O(n^3)

通常适合 $n\le 300$ 左右；经过优化或题目时限宽松时可以稍大。

4. 正向概率 DP 和反向期望 DP

两者不要混淆。

正向分配概率

已知当前落在状态 $i$ 的概率为 $dp[i]$ ，则：

dp[j] \mathrel{+}=dp[i]\cdot p(i,j)

适合：

恰好走 $k$ 步
经过有限轮后的位置分布
转移方向天然有序

例如：

dp[t+1][j] += dp[t][i]\cdot p(i,j)

时间复杂度一般是 $O(km)$ ，其中 $m$ 是转移数。

反向计算结果

定义从当前状态出发的答案：

E[i]=1+\sum_jp(i,j)E[j]

适合：

首次到达终点
直到过程结束的期望
最终成功概率

一个实用判断是：

“经过 $k$ 步后在哪里”通常正推。
“从这里出发最终怎样”通常反推或列方程。

5. 随机游走是否一定会结束

列期望方程之前，必须检查答案是否有限。

可能出现：

永远到不了终点
有正概率永远循环
虽然几乎必然到达，但期望时间仍然可能无穷

有限状态的常见判断方法是：

把终止状态视为吸收点。
检查从起点能到达的所有状态。
判断是否存在无法到达任何终止状态的闭合连通区域。

如果能以正概率进入一个没有出口、又不包含终点的 SCC，那么终止概率小于 1，期望终止时间通常就是无穷。

图论上可以：

求强连通分量；
缩点；
检查是否存在可达的“非终止汇 SCC”。

不少题目会保证答案有限，但最好主动确认题目条件。

6. 图上的随机游走

假设在无向图中，每次从当前点等概率选择一条相邻边：

E[u]=1+\frac{1}{\deg(u)}\sum_{v\sim u}E[v]

终点 $t$ 满足：

E[t]=0

两边乘上 $\deg(u)$ ：

\deg(u)E[u]-\sum_{v\sim u}E[v]=\deg(u)

这是与图的拉普拉斯矩阵有关的线性方程。

如果题目问从 $u$ 到 $v$ 再返回 $u$ 的期望步数，也就是 commute time，在无权无向连通图中有经典结论：

H(u,v)+H(v,u)=2mR_{\mathrm{eff}}(u,v)

其中：

$H(u,v)$ 是从 $u$ 首次到达 $v$ 的期望步数；
$m$ 是边数；
$R_{\mathrm{eff}}$ 是把每条边看作 $1\Omega$ 电阻后的等效电阻。

不过 ICPC 中若没有明显的树、电阻或拉普拉斯结构，通常直接列方程更稳。

7. 一维随机游走常用结论

例如位置在 $[0,n]$ ，每次：

以概率 $p$ 向右；
以概率 $q=1-p$ 向左；
到达 $0,n$ 后停止。

到达 $n$ 的概率满足：

P_i=pP_{i+1}+qP_{i-1}

边界：

P_0=0,\qquad P_n=1

当 $p=q=\frac12$ 时：

P_i=\frac{i}{n}

公平随机游走到达任意边界的期望步数：

E_i=i(n-i)

竞赛中不一定需要背公式，但应该认识到这是一个二阶线性递推，可以用：

特征方程；
差分；
高斯消元；
根据边界条件求常数。

8. “访问次数”类问题

设 $F_i$ 表示状态 $i$ 的期望访问次数。

可以使用“流入概率”的视角：

F_i=[i=s]+\sum_jF_jp(j,i)

其中 $[i=s]$ 表示起点贡献的一次访问。

它与到达时间方程方向不同：

到达时间从当前状态看后继；
访问次数统计从其他状态流入当前状态。

如果题目问某条边被经过的期望次数，则可以用：

\text{期望经过 }(u,v)\text{ 的次数}=F_u\cdot p(u,v)

期望的线性性非常重要：即使事件之间不独立，也可以直接累加期望。

9. 状态设计技巧

随机游走题难点经常不是概率，而是状态数。

位置信息

单个棋子：

dp[x]

两个棋子：

dp[x][y]

如果两者没有身份区别，可以令 $x\le y$ ，减少重复状态。

集合信息

需要记录访问过哪些关键点：

dp[pos][mask]

适用于关键点数量较小，通常 $k\le 15\sim 20$ 。

记忆性质

如果下一步只与当前位置有关，就是马尔可夫状态。

如果规则还依赖：

上一步方向；
连续失败次数；
当前持有物品；
最近一次颜色；

这些信息都必须加入状态，否则转移方程不成立。

一个判断标准是：

知道当前状态后，能否完全确定下一步的概率分布？

如果不能，状态就缺信息。

10. 常见优化方法

滑动窗口

例如：

E[i]=1+\frac1k\sum_{j=1}^{k}E[i+j]

直接计算是 $O(nk)$ ，维护区间和后可以降到 $O(n)$ 。

矩阵快速幂

如果要求走 $k$ 步后的概率分布：

v_{t+1}=v_tP

那么：

v_k=v_0P^k

适合：

状态数较小；
$k$ 极大；
转移矩阵固定。

复杂度约为：

O(n^3\log k)

若矩阵稀疏或有特殊结构，还可以进一步优化。

SCC 分块求解

有环并不意味着必须对所有状态一起做高斯消元。

可以：

对状态图求 SCC；
缩点后得到 DAG；
按逆拓扑序处理；
只在每个 SCC 内建立方程组。

如果每个 SCC 都很小，会比全局 $O(n^3)$ 快很多。

11. 浮点数注意事项

概率和期望题通常使用 double。

高斯消元时要：

选择绝对值最大的主元；
判断主元是否接近 0；
避免直接用 x == 0；
一般使用 eps = 1e-10 或 1e-12。

输出时注意：

题目要求的误差；
fixed << setprecision(...)；
极小负数可能是误差，例如 -1e-12 可以视情况修正为 0。

12. 一套实战解题流程

拿到随机游走题，可以按这个顺序思考：

明确随机过程什么时候结束。
定义状态，使下一步只依赖当前状态。
明确要求概率、期望时间还是访问次数。
写出最原始的转移方程。
找出边界状态。
判断状态图是否有环。
无环用 DP；小自环直接移项；一般环用线性方程组。
检查是否存在无限循环或无限期望。
根据数据范围考虑滑动窗口、矩阵快速幂、SCC 分块等优化。
用极小样例手算验证方程中的常数项和转移概率。

最值得记住的三个公式是：

P(s)=\sum_t p(s,t)P(t)

E(s)=1+\sum_t p(s,t)E(t)

F_i=[i=s]+\sum_jF_jp(j,i)

把随机过程准确翻译成这三类方程，随机游走题通常就已经解决了一半。

第一阶段：一维与棋盘随机游走

重点是首次到达、障碍、反弹、重启和大坐标。

顺序	题目	难度	Tag	核心训练
1	POJ 3744 - Scout YYF I	★★	`一维随机游走` `首次到达` `矩阵快速幂`	大坐标上跳 1/2 步，计算避开地雷的概率
2	AtCoder ABC275 E - Sugoroku 4	★★	`有限步随机游走` `边界反射` `概率DP`	正确处理越界后的反射位置
3	AtCoder ABC189 F - Sugoroku2	★★★★	`期望 hitting time` `重启` `仿射DP` `无穷判断`	随机走到陷阱后回到起点
4	LightOJ 1151 - Snakes and Ladders	★★★	`吸收马尔可夫链` `高斯消元` `棋盘随机游走`	蛇和梯子形成一般环，建立全局方程组
5	Codeforces 24D - Broken Robot	★★★★	`二维随机游走` `期望步数` `三对角方程` `逐行消元`	网格横向成环、纵向单调的经典模型

第 5 题非常重要：它展示了“状态图有环，但可以利用局部结构分层消元”，比直接全局高斯更有竞赛价值。

第二阶段：一般图上的到达时间

重点是图上首次到达时间：

H(u)=1+\sum_v p(u,v)H(v)

顺序	题目	难度	Tag	核心训练
6	洛谷 P4206 - NOI2005 聪聪与可可	★★★	`图上随机游走` `期望到达时间` `最短路预处理` `记忆化搜索`	随机游走与确定性追赶同时存在
7	HDU 4035 - Maze	★★★★	`树上随机游走` `回到根节点` `仿射树形DP`	将子树状态表示成父状态和根状态的线性函数
8	Codeforces 605E - Intergalaxy Trips	★★★★	`最优随机游走` `期望最短路` `贪心` `Dijkstra思想`	转移有概率失败时，如何最小化期望到达时间

推荐顺序是 P4206 → HDU4035 → CF605E。

其中 HDU4035 是树上随机游走的代表题，核心形式类似：

E_u=A_uE_{\operatorname{parent}(u)}+B_uE_{\text{root}}+C_u

通过树形 DP 合并并消元。

第三阶段：期望访问次数

这一阶段从“多久到达”切换到“每个点或每条边会经过多少次”。

点访问次数满足流量方程：

F_i=[i=s]+\sum_jF_jp(j,i)

注意转移方向是从前驱流入当前点。

顺序	题目	难度	Tag	核心训练
9	UVA 10828 - Back to Kernighan-Ritchie	★★★★	`期望访问次数` `有向图` `高斯消元` `无穷判断`	建立访问次数的流入方程
10	洛谷 P3232 - HNOI2013 游走	★★★★★	`无向图随机游走` `边访问次数` `高斯消元` `排序贪心`	从点访问次数推出边经过次数并最优化赋权

P3232 中，若 $F_u$ 是点 $u$ 被访问的期望次数，那么无向边 $(u,v)$ 的期望经过次数为：

C_{uv} = \frac{F_u}{\deg(u)} + \frac{F_v}{\deg(v)}

终点不再向外转移，因此要单独处理。计算所有 $C_{uv}$ 后，再利用重排不等式进行赋权。

第四阶段：综合挑战

顺序	题目	难度	Tag	核心训练
11	HDU 4089 - Activation	★★★★★	`循环概率DP` `队列状态` `自环消元`	多种事件导致状态前进、停留或整体重置
12	洛谷 P4550 - 收集邮票	★★★★★	`随机过程` `一阶矩` `二阶矩` `Coupon Collector`	费用与当前时间相关，需要同时维护高阶矩
13	UVA 11176 - Winning Streak	★★★★	`随机过程` `最大值期望` `分布DP`	通过 $\Pr(X\ge k)$ 或分布求最大连续段期望
14	洛谷 P2473 - SCOI2008 奖励关	★★★★	`有限时域随机过程` `状压期望DP` `最优策略`	随机事件、集合状态与最优决策结合

后面三道并非纯粹的图上随机游走，但能强化复杂随机过程的建模能力。

最推荐的十题主线

如果只刷一条高质量路线：

POJ 3744
→ ABC189 F
→ LightOJ 1151
→ CF 24D
→ 洛谷 P4206
→ HDU 4035
→ UVA 10828
→ 洛谷 P3232
→ CF 605E
→ HDU 4089

每道题重点检查什么

随机游走题建模完成后，依次检查：

终止状态是不是吸收状态。
方程求的是到达时间还是访问次数。
状态图是无环、局部成环还是全局成环。
自环能否直接移项。
是否需要高斯消元，或者能利用网格、树、SCC 等结构局部消元。
是否存在正概率永远无法终止。
数据范围是否要求矩阵快速幂或稀疏处理。

最值得优先攻克的是 CF24D、HDU4035 和 P3232。它们分别对应随机游走中的三个关键能力：局部消元、树上消元、访问次数方程。

本页目录