# 下坡路线计数：拓扑动态规划

## 从无向道路得到有向无环图

对每条道路，若两端高度不同，就从较高端连向较低端；若相等，则舍去这条不可用道路。每条有向边都严格降低高度，因此不可能有有向环。平行道路保留为多条边，因为路线序列包含道路编号。

令 $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)$ 恰为上述递推式的值。每条非空路线由其最后一条边及前面的路线唯一确定，既没有遗漏也没有重复。最终求和便得到全部路线。没有顶点时队列和求和都为空，答案为零。

![按终点计数的五点例子](assets/example.zh.svg)

## 实现与复杂度

每个顶点至多入队一次，每条边只处理常数次，时间和空间都是 $O(n+m)$ .用显式队列处理长链，不依赖深度为 $n$ 的函数递归。模数为 $998246353$ ，每次相加后立即取模；两个剩余的和小于 $2^{31}$ ，32 位有符号整数足够。

首选 [std.cpp](std.cpp) 保留出题人的拓扑排序与路线计数。GPT-6 完成证明、显式队列实现及边界检查。按高度排序计算同一递推需要额外排序，只改变拓扑顺序的获得方式，故不单列为不同解法。验证使用按高度递增的后继路线计数，与程序的前驱传播独立；覆盖空图、长链、重边、自环、等高图和模数回绕。性能见[测量记录](../../../docs/benchmark-R25.json)。