下坡路线计数：拓扑动态规划¶
从无向道路得到有向无环图¶
对每条道路，若两端高度不同，就从较高端连向较低端；若相等，则舍去这条不可用道路。每条有向边都严格降低高度，因此不可能有有向环。平行道路保留为多条边，因为路线序列包含道路编号。
令 \(F(v)\) 为以 \(v\) 结束的路线数。每个顶点本身贡献一条不移动的路线。其余路线有唯一的最后一条道路，于是
\[
F(v)=1+\sum_{(u,v)\text{ 为一条有向边}}F(u)\pmod{998246353}.
\]
总答案为所有 \(F(v)\) 的和；不同终点的路线互不相同。
计算顺序与正确性¶
统计各顶点的入度，把所有入度为零的顶点放入队列，初始 \(F(v)=1\) .每次取出 \(u\) ，对每条出边 \((u,v)\) 将 \(F(u)\) 加入 \(F(v)\) ，并将 \(v\) 的入度减一；减到零时将 \(v\) 入队。
顶点出队时，所有入边均已处理。因此按出队顺序归纳，\(F(v)\) 恰为上述递推式的值。每条非空路线由其最后一条边及前面的路线唯一确定，既没有遗漏也没有重复。最终求和便得到全部路线。没有顶点时队列和求和都为空，答案为零。
实现与复杂度¶
每个顶点至多入队一次，每条边只处理常数次，时间和空间都是 \(O(n+m)\) .用显式队列处理长链，不依赖深度为 \(n\) 的函数递归。模数为 \(998246353\) ，每次相加后立即取模；两个剩余的和小于 \(2^{31}\) ，32 位有符号整数足够。
首选 std.cpp 保留出题人的拓扑排序与路线计数。GPT-6 完成证明、显式队列实现及边界检查。按高度排序计算同一递推需要额外排序，只改变拓扑顺序的获得方式，故不单列为不同解法。验证使用按高度递增的后继路线计数，与程序的前驱传播独立；覆盖空图、长链、重边、自环、等高图和模数回绕。性能见测量记录。