概念：

属于最短路的拓展应用，常用于类似下面的模型:

已知一个带权图，现在需要求出从点 $u$ 到点 $v$ 是否存在一条路径，满足路径长度为$L$，每条边可以重复经过。其中数据满足：
$$L\le 10^{18}\forall w\le 10^4$$
当然，题目也可以换成求出一个区间 $[minL,maxL]$ 内的方案数，最小的合法长度，看题目的具体要求。

以简单的例题开始

题面[luogu P3403 跳楼机]

Srwudi的家是一幢$h$层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。

经过改造，srwudi的跳楼机可以采用以下四种方式移动：

1. 向上移动$x$层；
2. 向上移动$y$层；
3. 向上移动$z$层；
4. 回到第一层。

一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。
$$h\le 2^{63}-1,x,y,z\le 10^5$$

题解（瞎吹）

如果不考虑$h$的大小问题，那么我们可以得到一个简单的dp:
$$\begin{gathered} f(i)=f(i-x)Vf(i-y)Vf(i-z) \\ f(1)=true \\ （或运算符用V表示） \end{gathered}$$
因为$h$过大，这个dp的时空复杂度过高，不能接受，因此需要进行优化。

最终上升到的楼层和操作的顺序没有关系，所以我们可以将一种操作堆积起来，将一个到达的楼层分解为:
$$h=ax+by+cz$$
首先我们用最短路的方式求出数组$f()$，不知道怎么计算的到时候看代码
f ( i ) = min ⁡ h { h m o d    z = i } 其 中 h = a x + b y f(i)=minlimits_h{hmod z=i}\ 其中h=ax+by f(i)=hmin​{hmodz=i}其中h=ax+by
翻译成人话就是用前两种操作到达一个高度h，这个高度和z取模的结果是i，$f(i)$表示的是最小的h。

求出这个$f()$之后，我们从楼层$f(i)$出发，只用操作3能够到达的楼层有:
$$\lfloor \frac{h-f(i)}{x}\rfloor +1(1)$$
那么这个答案是否有遗漏呢，假设我们从$f(i)$出发，用操作1，2再走到了一个楼层$h^{\prime }$，这个楼层依然满足$h^{\prime }\mathrm{m}\mathrm{o}\mathrm{d}z=i$，那么可以得到:
$$\begin{gathered} h^{\prime }=\lfloor \frac{h^{\prime }}{z}\rfloor z+i \\ \because h=\lfloor \frac{h}{z}\rfloor z+i \\ \therefore h^{\prime }-h=(\lfloor \frac{h^{\prime }}{z}\rfloor -\lfloor \frac{h}{z}\rfloor )z \end{gathered}$$
所以这个楼层$h^{\prime }$其实也可以由$h$使用几次操作3得到，也就说它会被计算到式子(1)中，不会被遗漏，那么我们最终的答案可以表示为:
$$ans=\sum _{i=0}^n\lfloor \frac{h-f(i)}{x}\rfloor +1$$
这样的计算是不会用重复的。简单的证明（乱搞）如下：

使用反证法，如果同一个楼层能使用两种不同的方式得到，如果$x,y,z$互不相等，那么:
$$a_{1}x+b_{1}y+c_{1}z=a_{2}x+b_{2}y+c_{2}z=h$$
两个多项式相等，则这两多项式最高次数相同，且对应次数项的系数相同.

那么得到
$$a_1=a_2,b_1=b_2,c_1=c_2$$
显然两个方法其实是同一个。

如果$x,y,z$有两个是相等的，那么就可以将这两个相等字母所在的单项式合并，依然是类似于上面的结果。

一道难一点的题

题面[luogu P2371 墨墨的等式]

墨墨突然对等式很感兴趣，他正在研究等式

$$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n=B$$

存在非负整数解的条件，他要求你编写一个程序，给定$N$、 { a n } {an} {an}、以及$B$的取值范围，求出有多少B可以使等式存在非负整数解。

$$\begin{gathered} N\le 10, \\ \forall a_i\le 5\times 10^5, \\ 1\le B_{min}\le B_{max}\le 10^{12} \end{gathered}$$

题解（瞎吹）

显然用$[0,B_{max})$的方案数减去$[0,B_{min}-1)$的方案数就是题目要求的答案了。

找到序列$a$中最小的元素$m$，然后将序列中的每个元素分别对其取模，得到一个新的序列$t$。这样的话，如果一个$B$是合法的，那么$B+mx(x\in N)$也是合法的。而我们只需要知道一个对$m$取模为$i$的最小$B$是多少，那么就知道在区间$[0,B_{max}]$中有多少个数对$m$取模为$i$。

首先我们做一个最短路，对于点$u(u<m)$和点$(u+a_i)\mathrm{m}\mathrm{o}\mathrm{d}m$建一条边权为$a_i$的边，然后求出数组$f(u)$，其意义和上一道题目差不多。

而求出$[0,B_{max})$中的方案数可以使用这一条式子，而$[0,B_{min}-1)$的方案树也是类似的：

$$\sum _{i=0}^{m-1}\lfloor \frac{B_{max}-f(i)}{m}\rfloor +1$$

关于不重复和不遗漏的问题就交给正在看的各位dalao了。

再难一点的题目

题面

有一个有$n$个点的无向图，共有$m$条边，每一条边$e_i$的边权为$w_i$,现在要找到一条从点$1$到点$n$的路径，其长度恰好为$L$。问是否存在这样的路径。
$$n\le 50,w_i\le 3\times 10^4,len\le 10^{18}$$

题解（可能会TLE）

首先定义同余最短路的距离数组$dis[u][m]$表示从开始到点$u$，经过的路径长度$l$是满足$l\equiv m(modM)$的最小$l$，显然可以通过spfa求出。

对于与点$n$直接相连的一个点$v$，它们之间的边$e$的长度为$w$，显然到达该点之后在$e$上来回走奇数数次后可以到达点$n$，如果经过一条合法的路径（题目要求的路径）是经过这一条边的，那么$l$可以分解为$l_1+2aw$,而这个$l_1$要满足：$l_1\equiv l(mod2w)$，所以这个$l_1$可以被认为是$dis[v][l\mathrm{m}\mathrm{o}\mathrm{d}2w]+2w$，那么如果式子可以表示$l$那么就需要满足$dis[v][l\mathrm{m}\mathrm{o}\mathrm{d}2w]\le l$，于是同余最短路中的$M=2w$。

那么最终的算法表示为：
枚举一个端点为$n$的边，按照如上的方式计算出$dis$数组，接着判断。

最后

以上就是谦让小刺猬为你收集整理的同余最短路概念：以简单的例题开始一道难一点的题再难一点的题目的全部内容，希望文章能够帮你解决同余最短路概念：以简单的例题开始一道难一点的题再难一点的题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。