浅谈同余最短路
Exp10re
·
2023-10-20 15:31:07
·
算法·理论
前言
本文将会对同余最短路算法进行较简单的解释。
同余最短路的例题少到离谱。
编写此篇博客的原因很大一部分是因为某一天晚上梦见了一道同余最短路的题目，那么，就从那一题开始吧。
引入
例题：P3403 跳楼机。
简要题意：
你现在有一个数 h ，初始值为 1 。现在你可以进行以下四种操作若干次：
使 h=h+a 。
使 h=h+b 。
使 h=h+c 。
使 h=1 。
现给出一个常数 H 以及题面中的 a,b,c ，你需要求出有多少个正整数 k 满足 0\le k\le H 且满足 h 可以在进行若干次操作后有 h=k 。
其中：1 \le H \le 2^{63}-1 ，1 \le a,b,c \le 10^5 。
当 H 较小（比如 H \le 2 \times 10^5 ）时，这个问题可以使用背包解决。然而现在 H 的规模为 1 \le H \le 2^{63}-1 ，使用背包无法通过，那么我们就需要一种更高效的算法解决这种问题。
于是就有了同余最短路。
介绍
同余最短路算法是用于求解形如“给出 n 个数 a_{1,2,\cdots,n} ，求有多少个正整数 b 满足 b \le T 能使得 \displaystyle\sum_{i=1}^n a_ix_i=b 存在非负整数解”一类的问题。其时间复杂度以及空间复杂度取决于所使用的最短路算法，一般时间复杂度是 O(a_in \log n) 或更小，空间复杂度是 O(a_in) ，在下文会给出解释。
以上述题目为例，就是 n=3 的一种特殊情况。于是上述题目可以转化成：给出 a,b,c ，求满足 ax_1+bx_2+cx_3=k 且 0\le k\le H 的 k 的个数。其中 x_{1,2,3} 均为非负整数。\color{gray}\text{*}
------------
我们记一个数 $k$ 是合法的，当且仅当其能被表示成 $ax_1+bx_2+cx_3=k$ 的形式。那么就可以得到一个显然的结论：如果 $k$ 是合法的，那么 $k+ap$ 也一定是合法的。其中 $p$ 是一个非负整数。
证明：既然 $k$ 能被表示成 $ax_1+bx_2+cx_3=k$ 的形式，那么 $k+ap$ 就一定能被表示成 $a(x_1+p)+bx_2+cx_3=k$ 的形式。
注意到 $k\equiv k+ap(\bmod\ a)$，那么就有一个显然的结论：如果我们某个数 $k$ 合法，记 $q=k \bmod a$，那么所有满足 $p \bmod a=q$ 且 $p \in \lbrack k,H \rbrack$ 的正整数 $p$ 都是合法的，其个数为 $\lfloor \frac {H-k} a \rfloor+1$。$\color{gray}\text{**}
该结论不难被证明，请读者自证。
------------
记 $d_i$ 表示满足 $k \equiv i(\bmod\ a)$ 且合法的最小的 $k$，如果能用某种方法计算出 $d_{0,1,\cdots,a-1}$，那么答案就是 $\displaystyle\sum_{i=0}^{a-1} {\lfloor \frac {H-d_i} a \rfloor+1\ (d_i\leq H)}$。
现在，我们需要找到某种方法，来计算出 $d_{0,1,\cdots,a-1}$。
记当前正在考虑的数是 $k$，$\bmod\ a$余数为 $p$：
- 若使用了一次 $k = k+a$，那么 $k\bmod a$ 余数不变，仍为 $p$。
- 若使用了一次 $k = k+b$，那么 $k\bmod a$ 余数由 $p$ 变为 $(p+b)\bmod a$。
- 若使用了一次 $k = k+c$，那么 $k\bmod a$ 余数由 $p$ 变为 $(p+c)\bmod a$。
考虑转移：
- 若使用了一次 $k = k+a$，那么本次操作对于 $d$ 无意义。
- 若使用了一次 $k = k+b$，那么有 $d_p \stackrel{b}{\longrightarrow} d_{(p+b)\bmod a}$。
- 若使用了一次 $k = k+c$，那么有 $d_p \stackrel{c}{\longrightarrow} d_{(p+c)\bmod a}$。
容易发现这个转移与最短路类似。如果我们将每个在 $[0,a-1]$ 范围内的数都抽象为点（即 $\bmod\ a$ 的余数），每一次转移都抽象为边，并且认为 $d$ 代表“距离”，那么就可以使用最短路来实现转移：
- $d_0=0$，即视作 $0$ 为源点。
- 初始时 $d_{1,2,\cdots,a-1}$ 均为 $\inf$。
- $\forall x\in[0,a-1]$，连接一条形如 $x \stackrel{b}{\longrightarrow} (x+b)\bmod a$ 的边。
- $\forall x\in[0,a-1]$，连接一条形如 $x \stackrel{c}{\longrightarrow} (x+c)\bmod a$ 的边。
接下来对构建出的图以 $0$ 为源点跑一遍最短路，得到的 $d_i$ 就一定是满足 $d_i \equiv i(\bmod\ a)$ 且的最小的，合法的数。
要计算出答案，枚举 $i\in{[0,a-1]}$ 计算 $\displaystyle\sum_{i=0}^{a-1} {\lfloor \frac {H-d_i} a \rfloor+1\ (d_i\leq H)}$ 即可。
此处以 [P3403 跳楼机](https://www.luogu.com.cn/problem/P3403) 为例给出核心部分代码实现：
```cpp
long long query(long long x)//查询
{
long long ans=0;
long long i;
for(i=0;i<M;i++)
{
if(dis[i]<=x)// 在满足 di<=x 的情况下才对答案有贡献。
{
ans+=((x-dis[i])/M+1);
}
}
return ans;
}
int main()
{
int i,j;
n=3;// 例题给出的是 n=3 的特例。
scanf("%lld",&H);
H--;// 可以视作从第 0 层开始，到达不超过 H-1 的楼层数。
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(a[i]==0)//注意：因为一次增加 0 的转移无意义，在输入时应将其无视。
{
i--;
n--;
continue;
}
}
sort(a+1,a+1+n);// 为了减少边与点的数量，在选取模数的时候一般选取转移系数中的最小值。
M=a[1];
for(i=2;i<=n;i++)
{
for(j=0;j<M;j++)// 连边
{
edge[j].push_back((edg){(j+a[i])%M,a[i]});
}
}
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
Shortest_Path();//可以使用 dijkstra 等稳定的单源最短路算法，甚至 SPFA。
printf("%lld",query(H));
return 0;
}
```
考虑完 $n=3$ 的特殊情况，让我们看看普遍情况：
## 练习题 #1
传送门：[P2371 [国家集训队] 墨墨的等式](https://www.luogu.com.cn/problem/P2371)。
### 题目大意：
给定 $n, a_{1\dots n}, l, r$，求出有多少 $b\in[l,r]$ 可以使 $\sum_{i=1}^n a_ix_i=b$ 存在非负整数解。
其中，$n \le 12$，$0 \le a_i \le 5\times 10^5$，$1 \le l \le r \le 10^{12}$。
### 思路：
与上面的做法类似：首先对 $a$ 进行排序使得 $a_1$ 为方程系数中的最小值，记 $M=a_1$，然后将每个在 $[0,M-1]$ 范围内的数都抽象为点，连边：
- $d_0=0$，即视作 $0$ 为源点。
- 初始时 $d_{1,2,\cdots,M-1}$ 均为 $\inf$。
- $\forall i\in[2,n], x\in[0,a-1]$，连接一条形如 $x \stackrel{a_i}{\longrightarrow} (x+a_i)\bmod M$ 的边。
接下来还是跑一遍最短路，然后统计答案。与上面例题做法差别不大，故不多赘述。
## 练习题 #2
传送门：[P2662 牛场围栏](https://www.luogu.com.cn/problem/P2662)。
题目大意建议结合原题题面理解。
### 题目大意：
给定 $N,M,l_{1\dots n}$，记集合 $A$ 满足 $\forall i\in[1,n],j\in[0,\min(l_i,M)],$ 有 $l_i-j \in A$。
记集合 $A$ 元素个数为 $p$，你需要找到最大的正整数 $k$ 使得 $\sum_{i=1}^p A_ix_i=k$ 不存在非负整数解。
输出这个最大的 $k$，或报告最大值不存在。
$0\leq n\leq 100,0\leq m\leq 3000,1\leq l_i \leq 3000$。
### 思路：
先暴力枚举出 $A$ 中所有元素，找到其中最小的一个记为 $m$。（与题面中的 $M$ 区分开）
显然的，若 $m=1$，那么所有正整数都能被表示，最大值不存在。
若 $\gcd(l_{1\dots n})\ne 1$ 且 $M=0$，则显然最大值不存在。
记 $d_i$ 表示满足 $k \equiv i(\bmod\ m)$ 且合法的最小的 $k$，那么答案即为 $\max((d_i-m)\in\mathbb{N^+})$。
而我们知道 $d_i$ 可以用同余最短路，这道题目就解决了……并没有。
注意到 $A$ 中元素在不去重的情况下最多有 $3000^2$ 个，这是我们无法接受的，因此要对其进行去重。
去重后找到其最小值 $m$ 之后还能进一步优化：若多个数 $\bmod\ m$ 的余数相同，只保留其中最小的一个。
在同余最短路的实现中，余数相同的数所连的边的两个端点相同（端点只与余数有关），而边权由数本身决定。在最短路算法中，对于重边，使用其他边转移一定不优于用其中边权最小的边进行转移。因此，多个数 $\bmod\ m$ 的余数相同只保留其中最小的一个的正确性显然。
同余最短路的部分与上面的题目没区别，故不多赘述。
## 后记
### #1 关于 SPFA 以及时间复杂度
先前有“SPFA 已死”的说法，但在同余最短路的实现当中并不是这样，又或者说，SPFA 在同余最短路的实现中“复活”了。
让我们来看两份提交记录（均不使用 O2，dijkstra 使用堆优化）：
- [[提交记录]](https://www.luogu.com.cn/record/128424248)
P2371 [国家集训队] 墨墨的等式 SPFA：用时 4.73s，内存 107.76MB。
- [[提交记录]](https://www.luogu.com.cn/record/128424315)
P2371 [国家集训队] 墨墨的等式 dijkstra：用时 6.38s，内存 106.26MB。
同样是 AC 记录，在空间区别不大的情况下，SPFA 的用时远远小于 dijkstra 做法，这很值得我们思考其原因。
“SPFA 已死”的前提是什么？是 SPFA 在特殊构造的图执行最短路时会被卡到 $O(nm)$，因此有了“SPFA 已死”的说法。
在同余最短路算法中，连边操作取决于余数，显然无法特殊构造图。而 SPFA 在非特殊构造的图中运行速度是很快的，从某种意义上能到达先前所流传的 $O(Vk)$，因此，使用 SPFA 来实现同余最短路中最短路的部分也不失为一种选择。
### #2 关于模数的选取
在上面的三道题目中，细心的读者可能会注意到其选取的模数都为可选数中最小的数。
这也是一种优化：因为同余最短路的连边操作中，连边数取决于模数 $M$ 以及数的个数 $n$。
以上方 [P2371 [国家集训队] 墨墨的等式](https://www.luogu.com.cn/problem/P2371) 的连边操作为例：
- $\forall i\in[2,n], x\in[0,a-1]$，连接一条形如 $x \stackrel{a_i}{\longrightarrow} (x+a_i)\bmod M$ 的边。
不难发现其总边数为 $M\times (n-1)$，而最短路算法的时间复杂度与边数正相关，那么显然，我们应该选择尽可能小的 $M$ 以最小化程序运行时间。
让我们再来看三份提交记录（均不使用 O2，使用 SPFA）：
- [[提交记录]](https://www.luogu.com.cn/record/128424248)
P2371 [国家集训队] 墨墨的等式 选择最小数作为模数：用时 4.73s，内存 107.76MB，100 pts AC。
- [[提交记录]](https://www.luogu.com.cn/record/130508289)
P2371 [国家集训队] 墨墨的等式 选择最大数作为模数：AC 部分用时 9.03s，内存 125.00MB，40 pts TLE。
- [[提交记录]](https://www.luogu.com.cn/record/130508436)
P2371 [国家集训队] 墨墨的等式 选择中位数作为模数：AC 部分用时 10.45s，内存 120.92MB，95 pts TLE。
选取尽可能小的模数所带来的优势显而易见。
### #3 “不如转圈”
摘自 [同余最短路的转圈技巧 by Alex_Wei](https://www.cnblogs.com/alex-wei/p/17531487.html)，使用转圈技巧可以做到时间复杂度严格 $O(na_i)$。
本文仅仅是对同余最短路的简要分析，对于转圈技巧就不进行展开了。
### #4 结语
同余最短路本身是小众算法，应用面不算广泛，因此相比算法本身，笔者更希望读者能理解并应用其中的转化思想。
我的高中数学老师在讲换元时曾说：我们不仅要学会换元，还要有换元意识。笔者认为，这一句话不仅对换元适用，它也可以用来描述算法竞赛：算法竞赛中，理解思想往往比理解算法更有用。
感谢观看。