洛谷P6154游走题解：DAG路径期望与计数DP详解

2999这是我在刷题打卡记录里的第2999次。说实话这个数字挂在记录表里的时候自己都愣了一下没想到每天和洛谷题、C编译器较劲这件事居然真的能一路坚持下来。这轮打卡轮到的是洛谷 P6154 游走一道题面极短、但内核很扎实的DAG路径期望题。它表面考的是概率期望真正动起手来却是计数DP、拓扑排序、分数取模和快速幂的连环组合几乎把信息学竞赛里最常用的几板斧全过了一遍。这篇文章就借着这道题把从读题、推导到编码、踩坑的完整过程全部抖出来给正在刷图论和计数问题的朋友一个参考。1. 题目拆解P6154 看似概率题其实是计数题1.1 先把题面翻译成人话洛谷 P6154 游走的题面很短大意是给定一张 n 个点、m 条边的有向无环图从这张图上的所有合法路径中随机选一条问这条路径长度的期望是多少结果对 998244353 取模。这里的“路径”指从任意一个点出发沿着有向边一直走直到没有出边为止路径长度按经过的边数计最短的路径就是一个孤零零的点长度为 0。我当初第一次读这道题的时候差点被“随机游走”四个字带偏满脑子都是醉汉随机游走模型、马尔可夫链、转移概率矩阵这些东西。后来冷静下来重新读题才发现题目说的是“等概率随机选择一条路径”不是“从某个点出发每一步随机挑一条出边”。这两件事在一般的DAG上是不等价的。举个反例如果一个点有两条出边一条通向终点另一条通向一个有100个出边的点那么在真实的随机游走过程里走第二条边后还会有后续分支整条路径被抽中的概率显然不一样但题目这里只关心“从所有路径里均匀抽一条”所以每条路径的地位完全平等。这一步理解非常重要直接决定了解法方向。一旦把它当成动态随机过程去推转移矩阵就会把题做复杂甚至样例都过不了。读题的时候多花三十秒确认“等概率的对象到底是什么”往往比多写几十行代码更有价值。1.2 一个关键转换期望等于总量除以总数期望的本质是加权平均。在“每条路径等概率”的前提下期望的计算可以写成期望 所有路径的长度总和 ÷ 路径总数这个转换看起来朴实无华却把一道概率题变成了纯粹的计数题。可以类比成一个班级统计步数第一组1个人走了2步第二组2个人各走了3步第三组4个人各走了5步现在随机抽一个同学问他走了几步。你肯定不会去模拟抽人过程而是先算总步数 1×22×34×528再算总人数 1247最后除一下得到期望 4。路径和人数在这里是同一个道理。所以整道题的核心任务就变成两件事数清这张 DAG 上一共有多少条路径以及这些路径的长度总和是多少。DAG 上的路径计数是信息学里很经典的入门 DP 模型从任意起点到某个终点的路径数量可以通过枚举入边来递推。P6154 不过是在这个基础模型上多加了一个长度维度的统计。不过这里有一个特别容易踩的边界长度为 0 的单点路径必须算进去。很多第一版代码挂掉都是因为只统计了长度大于 0 的路径导致路径总数偏小最后期望值整体偏大样例对着对着就对不上。1.3 从手推样例到正式状态定义先拿一条简单链来手推一遍1→2→3。这条图中的所有路径是单点路径{1}、{2}、{3}长度均为 0长度为 1 的路径{1,2}、{2,3}长度为 2 的路径{1,2,3}路径总数为 6长度总和为 1124期望就是 4/62/3。接下来把这种枚举过程形式化成 DP。设两个数组cnt[u]以节点 u 为终点的路径总数包含单点路径sum[u]以节点 u 为终点的所有路径的长度之和初始时令每个 cnt[u]1sum[u]0。这个 1 表示“只有 u 自己”的那条长度为 0 的路径sum 为 0 是因为这条路径长度为 0不贡献任何长度。按照拓扑序处理到节点 u 时对于每条出边 u→v凡是能以 u 结尾的路径接到 v 后面就得到一条新的以 v 结尾的路径。这样的路径有 cnt[u] 条每条长度比原来多 1所以转移式是cnt[v] cnt[u]sum[v] sum[u] cnt[u]用链的例子验证一下。初始 cnt[1]cnt[2]cnt[3]1sum 全为 0。处理 1→2 时cnt[2]112sum[2]0112等等这里 sum[1]cnt[1]011所以 sum[2]011。手算的以 2 结尾的路径是 {2} 和 {1,2}长度和确实是 011。cnt[2]2 也对。再处理 2→3cnt[3]123sum[3]0(sum[2]cnt[2])0123。以 3 结尾的三条路径 {3}、{2,3}、{1,2,3}长度和是 0123。最后 totalCnt1236totalSum0134和手推完全一致。到这里核心算法已经清晰了在 DAG 上按拓扑序做一次递推统计出全体路径的 cnt 总和与 sum 总和最后做一次模意义下的除法。2. 算法设计的关键细节2.1 拓扑序处理DAG 上 DP 的基本纪律DAG 上的递推必须严格遵守拓扑序。拓扑序的意义在于处理到某个节点时它的所有前驱都已经处理完毕该累加的信息已经累加完毕不会出现“用到还没算好的值”这种尴尬。P6154 的节点数可以到 1e5 级别如果对这些规则不敏感随手写一个 for 循环按编号顺序去转移在编号顺序和拓扑序不一致的图上会直接出错。实现时最常用的是 Kahn 算法。先统计每个点的入度 indeg把所有入度为 0 的点放进队列然后依次弹出节点每 pop 一个节点就把它的所有出边转移给后继同时把后继入度减 1减到 0 就入队。这样队列弹出的顺序天然就是一个合法拓扑序。有朋友会问用记忆化搜索 DFS 行不行当然也行在这道题里正确性没问题但显式拓扑排序有几个实际好处第一不需要担心递归深度过大导致栈溢出尤其在点数是 1e5 甚至更大的时候第二拓扑排序可以顺带把入度处理完代码结构更线性不容易出隐蔽的递归 bug第三调试的时候可以直接观察队列弹出的顺序是否符合直觉。我在比赛里倾向于显式写队列除非题目要求必须记忆化递归处理复杂状态否则拓扑排序是第一选择。2.2 两个 DP 状态到底在维护什么cnt 和 sum 这两个数组容易让人混淆尤其 sum 的转移为什么要写成 sum[u]cnt[u]而不是直接 sum[u]。这里的关键在于理解“延伸一条边”对长度总和产生的增量。假设以 u 为终点的路径一共有 3 条长度分别是 2、3、5那么 cnt[u]3sum[u]10。现在统一在后面接上边 u→v得到 3 条新路径长度分别是 3、4、6。这 3 条路径的长度总和是 13恰好等于原来的长度总和 10 加上 3也就是 sum[u]cnt[u]。每次接边每条路径长度都加 1所以总长度要加上路径的条数。cnt[u] 在这里扮演的就是“增量次数”的角色。想清楚这个逻辑之后代码就不容易写错了。另外还要注意cnt[u] 和 sum[u] 在后继累加时都可能会超过 int 范围。路径数量在极端图上可以非常大很多题解里都强调要用 long long这不是杞人忧天。我习惯在任何涉及计数的 DP 里直接开 long long宁可多占一点内存也不要最后因为溢出换来一个 WA。2.3 分数取模为什么用逆元而不是直接除答案是一个分数 totalSum/totalCnt但题目要求输出对 998244353 取模后的值。模运算对除法不友好不能直接“模完之后再除”而是要把除以 totalCnt 变成乘以 totalCnt 的逆元。998244353 是一个质数。根据费马小定理对于质数 MOD 和任意不是 MOD 倍数的 x有 x^(MOD-1) ≡ 1 (mod MOD)。所以 x 的逆元就是 x^(MOD-2) mod MOD。求这个幂用快速幂复杂度是 O(log MOD)一次就够。P6154 的数据范围内分母 totalCnt 模 MOD 之后不会是 0不会出现“分母无逆元”的边界情况所以放心用费马小定理求逆。这里有个很常见的思维误区有些初学者会把 totalSum 取模后直接除以 totalCnt或者把 totalSum 不取模、算完浮点数再取模。这两种写法都有问题。前者在模意义下不成立后者会因为 totalSum 和 totalCnt 实在太巨大而丢失精度甚至可能溢出 double 的范围。正确姿势是全程整数、全程取模最后用快速幂求一次逆元。3. C 完整实现与逐段解读3.1 完整可提交代码下面这份代码是我实际提交并通过的版本逻辑清晰没有花哨的优化适合作为模板参考。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; const ll MOD 998244353; int n, m; vectorint g[MAXN]; int indeg[MAXN]; ll cnt[MAXN]; ll sumLen[MAXN]; ll qpow(ll a, ll b) { ll res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } int main() { scanf(%d%d, n, m); for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); g[u].push_back(v); indeg[v]; } for (int i 1; i n; i) { cnt[i] 1; // sumLen[i] 0 初始就足够 } queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { cnt[v] (cnt[v] cnt[u]) % MOD; sumLen[v] (sumLen[v] sumLen[u] cnt[u]) % MOD; indeg[v]--; if (indeg[v] 0) q.push(v); } } ll totalCnt 0, totalSum 0; for (int i 1; i n; i) { totalCnt (totalCnt cnt[i]) % MOD; totalSum (totalSum sumLen[i]) % MOD; } ll ans totalSum * qpow(totalCnt, MOD - 2) % MOD; printf(%lld\n, ans); return 0; }需要注意这份代码用到 C 11 起支持的 range-based for 循环如果你所在的老旧评测环境只支持 C98需要把 for (int v : g[u]) 改写成迭代器写法。现在的洛谷和主流 OJ 都支持 C14 以上问题不大。3.2 逐步讲解从建图到统计建图部分只建了正向边存的是从 u 指向 v 的邻接表同时维护 v 的入度。之所以不需要反向图是因为转移发生在“从当前节点走向后继节点”的方向上只需要正向边就够了。如果用记忆化搜索通常需要反向边去枚举前驱但拓扑排序的写法更自然。DP 阶段是核心。每次从队列里取出一个节点 u遍历它的每条出边把以 u 结尾的路径全部“延长”到 v。cnt 和 sumLen 的转移遵循前面推导的公式。这里所有加法都紧跟取模防止中间结果超出 long long。注意 sumLen[u] cnt[u] 这一项数学含义是“从 u 延伸出来的路径长度贡献”加法完成后再取模顺序不能乱。入度减到 0 才入队是 Kahn 算法的标准操作。有些同学会担心如果图中存在环拓扑排序会剩下一些节点。但题目明确给定的是 DAG所以循环结束后队列一定为空所有点都会被处理到。如果是不放心可以加一个计数器统计实际处理的节点数若小于 n 说明图不是合法的 DAG但这题完全没必要。最后统计总数。totalCnt 是所有以任意节点为终点的路径数量之和也就是整张图的路径总数。totalSum 是所有路径长度总和。期望就是两者相除用快速幂求分母逆元。3.3 复杂度和内存时间复杂度上建图 O(m)拓扑排序每个点和每条边都访问一次是 O(nm)DP 和拓扑排序合在一起也是 O(nm)最后快速幂 O(log MOD)。总复杂度 O(nmlog MOD)在 n、m 到 1e5 甚至 2e5 级别时完全无压力。空间方面邻接表存全部 m 条边三个数组分别是 int 和 long long 长度 n总内存大概在几 MB 到几十 MB非常宽松。如果你在比赛里看到这道题但内存限制给得很小可以放心写 vector 邻接表不需要手写链式前向星。当然链式前向星也是信奥选手的必备技能只是这道题用不上。4. 踩坑记录与常见问题速查4.1 忘了初始化为 1单点路径引发的惨案我第一版代码一上来就犯了这个错。当时想着 cnt 数组默认全是 0直接在 DP 里对每个出边做 cnt[v]cnt[u]结果把单独的节点路径全漏掉了。最后算出来的期望比答案小不少样例怎么调都对不上。后来重新读题才意识到长度为 0 的路径是合法路径必须算进总数量。初始化把每个 cnt[i] 设为 1就是给每个点补上“自己到自己的零长路径”。这个细节不仅是这道题的命门也是很多“求所有路径数量”类题目共同的隐藏条件平时刷题遇到路径计数多留个心眼。还有一种常见写法是在弹出节点时临时 cnt[u](cnt[u]1)%MOD。两种都能过但我个人觉得在初始化阶段统一置 1 更不容易遗漏因为后面所有转移逻辑都保持一致不用区分某个点是不是第一次被访问。4.2 逆元写错、爆 long long快速幂求逆元的时候最容易写错的不是快速幂本身而是把底数和指数搞反。有人会把 qpow(totalCnt, MOD-2) 写成 qpow(MOD-2, totalCnt)写完整道题看起来没问题一跑就废。建议把快速幂当成固定模板多敲几遍闭着眼睛都能写出来为止。取模的粒度也要注意。cnt[v]、sumLen[v] 每次累加后取模这是必须的。有些朋友为了少写几个取模符号只在最后统计 totalCnt、totalSum 时取模中间过程放任不管。看起来没什么实际上当累加次数达到 1e5 级别时long long 也会被撑爆。养成“每加一次就取模”的习惯能省掉无数个深夜排查溢出的夜晚。4.3 拓扑排序队列处理的边界队列初始化时只把入度为 0 的点放进去。如果图中存在多个连通分量每个分量里入度为 0 的点都会作为起点进入队列这没问题。处理过程中只有 indeg[v] 减到 0 时才入队如果 indeg[v] 减成负数说明图里有环或者读入有重复边后者在本题不会出现。不过如果你在做其他题时发现 indeg 出现负数要优先怀疑是有环而不是代码 bug。还有一个容易被忽略的小问题如果 n 很大、图很稀疏很多点可能既没有出边也没有入边这些孤立点也是一条长度为 0 的路径。因为初始化时 cnt1 且它们一开始就在队列里入度为 0所以会被正确计入 totalCnt 和 totalSum。这部分我一开始也没想到后来手动构造了一个“一个点、零条边”的数据才发现初始化和孤立点会碰撞出一套正确结果。4.4 快读和输入优化的实用性P6154 的数据规模下scanf 已经完全够用但有不少信奥选手习惯性地上快读模板。快读的核心就是 getchar 逐字符解析整数比标准库的格式化输入快不少。对于 n、m 在 1e5 的比赛题快读和关流同步的 cin 差距不大但到了 1e6 以上数据量快读的收益就很直观了。如果你经常刷题建议把快读模板背下来读入可以统一用快读省得每次纠结要不要优化。不过在这道题里用 scanf 就够了别过度优化。我自己实际敲代码时还喜欢加一行 ios::sync_with_stdio(false)、cin.tie(0) 的配置因为 C 的 cin/cout 在关了同步之后其实也很快而且写起来比 scanf/printf 舒服。不过用了快读就不要混用 cin/cout 了混用会导致缓冲区混乱输出顺序可能出问题。5. 变式分析与一点体会5.1 变式一边带权后的期望如果题目改成每条边带一个权值路径长度定义为路径上边权和期望怎么算状态设计依然可以沿用 cnt 和 sum不过 sum 的转移要改成sum[v] sum[u] cnt[u] * w(u,v)。也就是说每条以 u 结尾的路径接上边 u→v 后长度增加的不再是 1而是这条边的权值 w所以总长度增量是 cnt[u]×w。cnt 的转移完全不变。这类带权扩展在模拟赛里很常见理解了原始公式带权版就是顺手改一行的事。5.2 变式二固定起点或逐边随机游走还有一种变式会把题目改成“从指定起点出发每一步等概率选择一条出边走到无出边为止求期望步数”。这种题的模型和 P6154 不一样因为每条路径被选中的概率不再均衡。设 E[u] 表示从 u 出发的期望步数转移是 E[u]0 当 u 没有出边否则 E[u] 1 (1/deg(u)) × Σ E[v]。在 DAG 上仍然可以用反向拓扑序求解。如果题目要求求所有点作为起点时的期望平均值还要再对 E[u] 取平均。刷题的时候一定要分清题面里“随机选路径”和“随机走边”的微妙差别这两种说法在普通有向图里往往对应完全不同的做法。5.3 刷题打卡的一些个人体会走到第 2999 次打卡我最大的感受是信奥刷题真正值钱的地方不在于背了多少模板而在于每道题都逼着自己把“为什么这样做”讲清楚。P6154 这种题目代码量不大但如果没有把期望转换、单点路径、逆元这几件事想通透写出来也大概率是错的。反过来想通一次之后以后再遇到路径计数、期望统计、DAG 递推这类题目都会很有底气。另外也分享一个小习惯每次 AC 之后我会故意把代码里的某个关键条件改掉比如把 cnt 初始化为 0 或者把取模去掉再跑一次样例观察结果怎么变坏。这样做的目的是主动理解每个细节的权重在考场上万一时间紧张也能快速定位问题。这个方法虽然笨但对巩固算法的理解非常有效。P6154 是一道性价比极高的练手题覆盖的知识点密集代码又短非常适合用来检验自己的图论 DP 基本功。如果你还没有刷过建议找一个安静的时间从读题开始自己推一遍再对照代码实现一遍最后再想想文中提到的变式。这比你机械地刷十道同类题目要有用得多。