【算法漫笔004】浅谈同余最短路
突然发现之前写的全部是字符串，于是乎就有了此篇插队在了 Manacher 的前面。
最短路
普通的最短路解决的问题通常是在一个图中寻找两个点之间权值和最短的路径。常见的算法例如 Floyd、Dijkstra、SPFA等都是解决类似问题的算法。而同余最短路解决的问题看似好像和最短路完全不沾边。
同余最短路
考虑以下问题：给定若干正整数 a1,a2…ana_1,a_2 \dots a_na1 ,a2 …an ，求在某个较大的范围 [L,R][L,R][L,R] 内，有多少个数可以被这些数非负整数线性组合表示（即可重复的选取任意 aaa 中的元素），或者求最大不能表示的数。
我们先简化问题，先将区间 [L,R][L,R][L,R] 改为 [0,X][0,X][0,X] 解决。但这似乎无法和最短路扯上关系。
的确，这样的问题似乎并不和最短路搭边，那我们能否将问题转化一下呢？
现在设想一下，如果我们选定了某一个数作为 modmodmod，比如取 mod=min(a1,a2,…an)mod=\min({a_1,a_2,\dots a_n})mod=min(a1 ,a2 ,…an )，那么任何一个能被表示的数 xxx，显然都可以写成 x=y+t×mod(0≤y≤mod,t≥0)x=y+t \times mod (0 \le y \le mod,t \ge 0)x=y+t×mod(0≤y≤mod,t≥0) 的形式。
现在，我们将每一个可表示的数 yyy 相同的分为一类，称为同余[1]类。比如在 mod=3mod=3mod=3 下，y=1y=1y=1 的同余类就包含了 1,4,7…1,4,7 \dots1,4,7…。显然此时每个同余类的元素数量是无限的。因此，对于每个同余类，我们只关心其中最小的可表示数，将其记为 dyd_ydy 。
如何求得 DYD_YDY ？
显然的一种方式是枚举整数 ttt，从小到大检查 t×mod+yt \times mod+yt×mod+y 能否被 aaa 中的数组合出来。但时间复杂度可以来到 O(X×n)O(X \times n)O(X×n)，效率显然不高。
我们注意到，从任意一个可表示的数 xxx 出发，加上任意一个 aia_iai 后仍然可表示。如果我们把余数看作状态，那么从余数 uuu 转移到余数 (u+ai)mod mod(u+a_i) \mod mod(u+ai )modmod 的代价就是 aia_iai 。
有点绕，举个例子。我们取 a=3,5a={3,5}a=3,5，则 mod=min(a1,a2)=min(3,5)=3mod=\min(a_1,a_2)=\min(3,5)=3mod=min(a1 ,a2 )=min(3,5)=3。同余类则有 y=0,1,2y=0,1,2y=0,1,2 三类。
此时：
若从余数 000 出发：
* 加 333：(0+3) (mod3)=0(0+3) \pmod{3} = 0(0+3) (mod3)=0，代价 333
* 加 555：(0+5) (mod3)=2(0+5) \pmod{3} = 2(0+5) (mod3)=2，代价 555
从余数 111 出发：
* 加 333：(1+3) (mod3)=1(1+3) \pmod{3} = 1(1+3) (mod3)=1，代价 333
* 加 555：(1+5) (mod3)=0(1+5) \pmod{3} = 0(1+5) (mod3)=0，代价 555
从余数 222 出发：
* 加 333：(2+3) (mod3)=2(2+3) \pmod{3} = 2(2+3) (mod3)=2，代价 333
* 加 555：(2+5) (mod3)=1(2+5) \pmod{3} = 1(2+5) (mod3)=1，代价 555
此时我们视代价为边权，构建一个有向图：
0→300→521→311→502→322→510 \xrightarrow{3} 0 \\ 0 \xrightarrow{5} 2 \\ 1 \xrightarrow{3} 1 \\ 1 \xrightarrow{5} 0 \\ 2 \xrightarrow{3} 2 \\ 2 \xrightarrow{5} 1 \\ 03 005 213 115 023 225 1
以 000 为源点跑一遍 DijkstraDijkstraDijkstra，可以得到：
dis0=0dis1=10dis2=5dis_0=0 \\ dis_1=10 \\ dis_2=5 dis0 =0dis1 =10dis2 =5
容易发现，disy=dydis_y=d_ydisy =dy 。那么求得 dyd_ydy 后，由于定义，对于每个 dy+t×modd_y+t \times moddy +t×mod 都可以表示。所以显然 [0,X][0,X][0,X] 内可表示的数量为：
⌊X−dymod⌋+1\left\lfloor\frac{X-d_y}{mod} \right\rfloor+1 ⌊modX−dy ⌋+1
总答案即为所有余数的贡献之和：
ans=∑y=0mod−1max(0,⌊X−dymod⌋+1)ans=\sum_{y=0}^{mod-1}\max\left(0,\left\lfloor\frac{X-d_y}{mod} \right\rfloor+1\right) ans=y=0∑mod−1 max(0,⌊modX−dy ⌋+1)
没有人觉得我Markdown写的很好吗
现在我们解决了 [0,X][0,X][0,X] 的问题，那么 [L,R][L,R][L,R] 呢？其实很简单，通过前缀和思想不难得到：[L,R]=[0,R]−[0,L−1][L,R]=[0,R]-[0,L-1][L,R]=[0,R]−[0,L−1]。这样我们就轻松的解决了这个问题！
恭喜你，你又可以水一道青题了！
P3403 跳楼机
AC记录
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
大家要多多点赞支持啊！这是我更新的动力qwq
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 同余，即若 amod m=ca \mod m=camodm=c 且 bmod m=cb \mod m=cbmodm=c 则 a,ba,ba,b 在模 mmm 的意义下同余。 ↩︎
