同余最短路

同余最短路可以用于解决形如 “给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他的整数（\(n\) 个整数可以重复选取）”以及“给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数”，或者“至少要拼几次才能拼出模 \(k\) 余 \(p\) 的数”的问题的时候可以使用同余最短路的方法。

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。

类比差分约束的方法，利用同余构造的这些状态可以看作单源最短路中的点，同余最短路的状态转移通常是这样的：\(f(i + y) = f(i) + y\)，类似单源最短路中的 \(f(v) = f(u) + edge(u,v)\)。