1. 同余最短路
说难也不算很难,挺有意思的一个知识点,不过应用不多。
前置知识:SPFA & Dijkstra 求最短路。
1.1. 算法简介
同余最短路常用来求解:给出 (n (nleq 50)) 个数 (a_i (1leq a_ileq 10^5)),求在某个范围((10^{18}))内有多少个数能够由这些数进行系数非负的线性组合得到。
由题意,对于一个数 (r),如果它可以被组合而成,那么任何 (r+x_ia_i) 也可以组合而成。但是同时考虑所有变量非常麻烦,时间复杂度也无法接受,所以我们将目光仅放在一个数 (a_1) 上。
同余最短路的核心思想是:如果一个数 (r) 可以得到,那么任何 (r+xa_1) 也可以被得到。因此我们只需要找:对于每个模 (a_1) 同余的同余类,其中最小的能被组合出的数是什么。注意到 (a_1) 本身是较小的,所以对每个同余类求出最小数是可行的。而如果我们得到了模 (a_1) 余 (j) 的数中最小能被表示出来的数,设为 (d_j),那么可以通过加上 (a_2sim a_n) 转移到其它同余类 (d_k (kequiv j+a_ipmod {a_1}) (2leq ileq n))。
注意到上述算法非常像一个最短路:对于每个点 (j),它向 ((j+a_i)mod a_1) 连了一条长度为 (a_i) 的边,求每个点的最短路。因此使用 SPFA(不可能是网格图或其它奇奇怪怪的图,不会被卡)或 Dijkstra 即可。初始值 (d_0=0),(d_i=infty (1leq i<a_1))。
求出 (d_j) 后得到答案是 trivial 的,不妨设我们需要求出 ([1,r]) 有多少个符合要求的数,则答案为:
除法下取整,时间复杂度为 (mathcal{O}(na_1k))。
1.2. 例题
I. P2371 [国家集训队]墨墨的等式
是同余最短路的板子题。设 (m=n imes a_i)。由于图的形态很固定(不是网格图),所以使用 (mathcal{O}(mk)) 的 SPFA 会比 (mathcal{O}(mlog m)) 的 Dijkstra 快不少。
const int N = 5e5 + 5;
ll n, l, r, ans, a[N], d[N];
queue <int> q;
int main(){
cin >> n >> l >> r;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
mem(d, 0x3f, N), d[0] = 0, q.push(0);
while(!q.empty()) {
ll t = q.front(); q.pop();
for(int i = 2; i <= n; i++) {
ll to = (t + a[i]) % a[1], v = d[t] + a[i];
if(d[to] > v) d[to] = v, q.push(to);
}
}
for(int i = 0; i < a[1]; i++) {
ll h1 = l - d[i] - 1, h2 = r - d[i];
if(h1 >= 0) ans -= h1 / a[1] + 1;
if(h2 >= 0) ans += h2 / a[1] + 1;
} cout << ans << endl;
return 0;
}