同余最短路学习笔记.Part3/题解：P3403 跳楼机
StarsIntoSea
·
·
题解
Upd 24.10.17：修改了部分笔误。
Upd 25.10.03：修改了部分笔误。
包括 OI Wiki 在内的同余最短路教程感觉都过于抽象，本蒟蒻学了很久才理解……于是写下了这篇算是比较详细的文章。
前置知识：单源最短路、同余。
在此之前可以去 OI Wiki 了解一下同余最短路的用途，这里不多赘述。
注意：本文章语言更偏向口语化，没有过多专业术语，如果您需要更加严谨的文章建议转向其他文章，感谢。
图论部分
（凡是提到类似“跑一遍最短路”的话可以认为是 Dijkstra 算法或 SPFA 算法，两者无异。）
（如果您曾经接触过差分约束并且已经理解掌握，那么您可以跳过该部分。）
先来看这么一张图：
这是以 1 号节点出发，跑一遍最短路会得到 dis 数组，dis[x] 表示从 1 号节点到 x 节点的最短路径。
我会暂时把这类跑一遍最短路的图称为最短路图。
在跑最短路时，我们总是会不断更新 dis 数组（即松弛操作），更新的条件是满足：dis[x]+edge(x,y)<dis[y]。
其中 edge(x,y) 表示从 x 向 y 的一条有向边的边权，如上图的 edge(5,3)=6。
但是最短路图有一个显然的性质：对于任意两个点 x,y，若 x 向 y 有有向边，那么一定满足不等式：
dis[x]+edge(x,y)\ge dis[y]
证明比较容易：如果没有能够进行松弛操作的一对点，就会停止跑最短路，相当于没有任意两个点满足：dis[x]+edge(x,y)<dis[y]，那反过来就得到了 dis[x]+edge(x,y)\ge dis[y]。
这个性质非常重要，这将会是解决同余最短路和差分约束的关键。
算法部分
引入一个问题：
给定四个正整数 x,y,z,H，求有多少个整数 d \in [0,H] 满足 ax+by+cz=d，其中 a,b,c 且都是非负整数。
（接下来的 a,b,c 均为非负整数，称一个数合法当且仅当其可以表示成 ax+by+cz 的形式，但不一定小于等于 H。）
一个重要的性质，若一个整数 k 能被若干个 y,z 拼成（k=by+cz），那么 k+x、k+2x、k+3x\cdots 都是合法的，当然 k 本身也是合法的。
我们令函数 f(i) 为 by+cz \bmod x =i 时最小的 by+cz。也可以理解为使用若干个 y 和 z 能够拼的数在模 x 意义下等于 i 的最小的值。
该函数有一个显而易见的性质：
f(i)+y \ge f((i+y)\bmod x)\\
f(i)+z \ge f((i+z)\bmod x)
因为如果存在一个 i 使得 f(i)+y < f((i+y)\bmod x) 就不符合定义，因为让 f((i+y)\bmod x) = f(i)+y 是更优的。z 的情况也同理。
我们发现这个性质与我们上面提到的最短路图的性质（dis[x]+edge(x,y)\ge dis[y]）相似。
这样我们可以建边：
edge(i,(i+y)\bmod x)=y\\
edge(i,(i+z)\bmod x)=z
即：
建完边之后，跑一遍最短路，得到的 $dis[i]$ 就相当于 $f(i)$。
那么有了 $f(i)$，如何计算答案。
根据我们刚开始得出的一个性质，若一个整数 $k=by+cz$，那么对于 $k+x$、$k+2x$、$k+3x\cdots$ 小于等于 $H$ 的数共有 $\lfloor\frac{H-k}{x}\rfloor$ 个。
这个公式其实很简单，大于 $k$ 小于等于 $H$ 的数有 $H-k$ 个，在这些数中每 $x$ 个数就有 $1$ 个，一共就是 $\lfloor\frac{H-k}{x}\rfloor$ 个。
那么本题的答案就是：
$$
\sum_{i=0}^{x-1} ( \lfloor\frac{H-f(i)}{x}\rfloor+1 )
$$
加一是因为 $f(i)$ 本身也是一个合法数。
让 $f(i)$ 尽可能小是为了防止漏解。
根据定义，$f(0)$ 一定等于 $0$，那么跑最短路时源点也就确定了是 $0$。
## 例题1 [P3403 跳楼机](https://www.luogu.com.cn/problem/P3403)
其实就是上面的那道题。
但是楼层是从 $1$ 开始的，我们可以假设从 $0$ 开始，统计到 $H-1$ 即可。
```cpp
#include <stdio.h>
#include <queue>
using namespace std;
#define int long long
const int N=1e5+5;
const int inf=9223372036854775807;
int H,x,y,z,idx=0;
int dis[N],vis[N],h[N];
struct node{int to,c,ne;}e[N<<1];
void add(int a,int b,int c){
e[++idx]={b,c,h[a]};
h[a]=idx;
}
void SPFA(){//最短路模板
for(int i=0;i<x;++i) dis[i]=inf;
queue<int> q;
q.push(0),dis[0]=0;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=h[x],y,w;i;i=e[i].ne){
y=e[i].to;
w=e[i].c;
if(dis[x]+w<dis[y]){
dis[y]=dis[x]+w;
if(!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
}
int main(){
scanf("%lld%lld%lld%lld",&H,&x,&y,&z);
if(x==1||y==1||z==1){printf("%lld\n",H);return 0;}//特判
--H;
for(int i=0;i<x;++i){
add(i,(i+y)%x,y);
add(i,(i+z)%x,z);
}
SPFA();
int res=0;
for(int i=0;i<x;++i)
if(H>=dis[i]) res+=(H-dis[i])/x+1;//这里特判一下是可能会有大于H的情况，导致出现负数
printf("%lld\n",res);
}
```
## 例题2 [P2371 [国家集训队] 墨墨的等式](https://www.luogu.com.cn/problem/P2371)
只是从 3 个的情况变成了 $n$ 个的情况。
统计时只需要先统计小于等于 $r$ 的情况，把答案减去小于等于 $l-1$ 的情况即可。
注意要额外特判等于 $0$ 的情况。
```cpp
int main(){
scanf("%lld%lld%lld",&n,&l,&r);qwq=-1;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
if(a[i]==1){
printf("%lld\n",r-l+1);
return 0;
}
if(a[i]!=0&&qwq==-1) qwq=i;//记录第一个不为0的位置
}
if(qwq==-1){printf("0\n");return 0;}
--l;
for(int i=0;i<a[qwq];++i)
for(int j=1;j<=n;++j)
if(j!=qwq) add(i,(i+a[j])%a[1],a[j]);
SPFA();
int res=0;
for(int i=0;i<a[qwq];++i){
if(r>=dis[i]) res+=((r-dis[i])/a[qwq]+1);
if(l>=dis[i]) res-=((l-dis[i])/a[qwq]+1);
}
printf("%lld\n",res);
}
```
## 例题3 [AT_arc084_b Small Multiple](https://www.luogu.com.cn/problem/AT_arc084_b)
令函数为 $f(i)$ 为一个数 $x \bmod n =i$ 时位数和的最小值。
那么有：
- $f(i) \ge f(10i\bmod n)
-
f(i) +1 \ge f((i+1)\bmod n)
即 i 向 10i \bmod n 建一条边权为 0 的边、i 向 (i+1)\bmod n 建一条边权为 1 的边。
注意这里应该让 f(1)=1 且以 1 为源点跑最短路，答案为 f(0)，因为我们是要求出 n 的正整数倍的答案，其在模 n 意义下为 0。而且 f(1) 显然等于 1。
其他注意事项
不难发现这个同余最短路是需要选出一个数作为模数，我们暂时令这个数为 x。
我看很多讲解是要求 x 尽可能小，但意义不是很大。跑这个最短路需要 x 个点，边的个数与点数相关，因此，选出的 x 实际上与整个程序效率有关，并不影响正确性。
感谢您能看到这里！如果有什么不懂的地方\有错误需要指正的地方就私信我，感谢！！qwq