同余最短路看名字感觉很难，但其实非常简单，也好理解，先说一道题：

题目

原型：洛谷P3403 跳楼机

有一栋 $h$ 层的大楼（层数编号从 $1$ 到 $h$），有 $n+1$ 种移动方式：

  • 回到 $1$ 层
  • 向上走 $x_1 \sim x_n$ 层

楼层不是循环的，你无论如何都无法到达 $h+1$ 层或以上。

最初你可以在任意一层（但也无关紧要），问你能到达多少个不同的楼层。

题解

分类

我们按楼层模 $x_1$ 的余数分类，把楼层 $i$ 分到 $i \bmod x_1$ 类。

这样分类有什么用呢？见下。

定义状态

有了这个分类，我们可以定义状态 $d_i$（$i \in [0,x_1)$）代表不用「向上走 $x_1$ 层」操作能到达的、最小的第 $i$ 类楼层是多少。

那么，由于有「向上走 $x_1$ 层」操作，所以 $d_i,d_i+x_1,d_i+2x_1,\dots$（比 $d_i$ 大或相等的第 $i$ 类楼层）都是可达的。

接下来考虑转移这个状态。

转移

其实也很好想，比如用一次「向上走 $x_2$ 层」操作，那么 $d_i$ 可以转移到 $d_{(i+x_2) \bmod x_1}$，转移代价为 $x_2$，所以：

$d_{(i+x_2) \bmod x_1}=\min(d_{(i+x_2) \bmod x_1},d_i+x_2)$

修改

但很快就能发现，这个DP不拥有拓扑序，所以必须要用最短路去解决，建图伪代码：

  • 枚举 $i \in [0,x_1)$
    • 枚举 $j \in [2,n]$
      • DP转移形如：$d_{(i+x_j) \bmod x_1}=\min(d_{(i+x_j) \bmod x_1},d_i+x_j)$
      • 于是就建从 $i$ 到 $(i+x_j) \bmod x_1$ 的有向边，边权为 $x_j$

易得点数为 $O(x_1)$，边数为 $O(x_1 \times n)$，以Dijkstra复杂度 $O((n+m) \log (n+m))$，总复杂度为 $O((x_1 \times n) \log (x_1 \times n))$，在 $n \leq 2 \times 10^3,x_1 \leq 2 \times 10^3$ 左右是完全稳过的。