# 有限体力的路线计数：按体力与高度排序状态

## 先确定计数对象

路线只由顶点序列区分。因此将每条无向道路端点排序，再将相同端点对去重。普通道路加入两个邻接方向，自环只加入一次。高度是整数，题面的消耗恰好为下坡零、等高一、上坡二。

虽然图中可能有环，但零消耗移动严格降低高度，不能形成环。每次正消耗移动至少用掉一单位体力，所以一条合法路线至多有 $E$ 次正消耗移动；相邻正消耗移动之间的下降段也是有限的。路线总数因此有限。

## 按剩余体力定义状态

令 $F_e(u)$ 为从顶点 $u$ 出发、总消耗不超过 $e$ 的路线数。选择直接停止贡献一条路线，其余按照第一次到达的顶点分类：

$$F_e(u)=1+\sum_{h_v<h_u}F_e(v)+\sum_{h_v=h_u}F_{e-1}(v)+\sum_{h_v>h_u}F_{e-2}(v).$$

每个求和只遍历去重后的邻居，负下标项为零，所有加法对 $998244353$ 取模。

按 $e=0,1,\ldots,E$ 计算每一层，在一层内按高度递增处理顶点。同层引用严格更低的高度，已算好；等高与上坡引用前一层或前两层，也已算好。只需保存三个滚动数组。

## 正确性

每个状态的路线恰分为立即停止，或沿某个可行邻居迈出第一步。这些类别按顶点序列互不重叠；去掉第一步后，后缀恰由剩余体力的相应状态计数。反向加回第一步也总得到合法路线。

先按体力、再按高度归纳，上述顺序保证所有依赖都先于当前状态，故递推求得准确的路线数。不同起点的顶点序列不同，最终答案为 $\sum_uF_E(u)$ .$E=0$ 时仍需计算任意下降路线，不能只返回顶点数；$n=0$ 时答案为零。

![两点图的七条合法路线](assets/example.zh.svg)

## 实现、复杂度与贡献

相等高度的内部顺序任意。自环消耗一，引用旧层，不会造成同层自依赖。三个数组循环覆盖时，当前层每个顶点都会重新赋值；需要的前两层尚未被覆盖。每次加法及时取模，两个剩余之和小于 $2^{31}$ .

排序顶点和道路需要 $O(n\log(n+1)+m\log(m+1))$ 时间，动态规划需要 $O((E+1)(n+m))$ 时间，空间 $O(n+m)$ .首选 [std.cpp](std.cpp) 适用全部范围。以“已花体力及终点”为状态的前向传播也是同一无环状态图上的动态规划，用于独立答案核对；保存全部体力层不会改善本题的时间或空间要求，故不另列发布程序。

提供的材料没有可用的求解程序或题解。GPT-6 用经典分层动态规划给出建模、证明、双语说明和 C++17 实现；分层动态规划本身是通用方法。测试覆盖零体力、空图、重边、自环、等高环、严格下降链及最大体力，性能见[测量记录](../../../docs/benchmark-R25.json)。