跳转至

同余最短路

当出现形如「给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他整数（\(n\) 个整数可以重复取）」，以及「给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 \(K\) 余 \(p\) 的数」的问题时可以使用同余最短路的方法。

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。

类比 差分约束 方法，利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的 \(f(i+y) = f(i) + y\)，类似单源最短路中 \(f(v) = f(u) +edge(u,v)\)。

例题

例题一

P3403 跳楼机

题目大意：给定 \(x，y，z，h\)，对于 \(k \in [1,h]\)，有多少个 \(k\) 能够满足 \(ax+by+cz=k\)。（\(0\leq a,b,c\)，\(1\le x,y,z\le 10^5\)，\(h\le 2^{63}-1\)）

不妨假设 \(x < y < z\)。

令 \(d_i\) 为只通过 操作 2 和 操作 3，需满足 \(p\bmod x = i\) 能够达到的最低楼层 \(p\)，即 操作 2 和 操作 3 操作后能得到的模 \(x\) 下与 \(i\) 同余的最小数，用来计算该同余类满足条件的数个数。

可以得到两个状态：

  • \(i \xrightarrow{y} (i+y) \bmod x\)

  • \(i \xrightarrow{z} (i+z) \bmod x\)

注意通常选取一组 \(a_i\) 中最小的那个数对它取模，也就是此处的 \(x\)，这样可以尽量减小空间复杂度（剩余系最小）。

那么实际上相当于执行了最短路中的建边操作：

add(i, (i+y) % x, y)

add(i, (i+z) % x, z)

接下来只需要求出 \(d_0, d_1, d_2, \dots, d_{x-1}\)，只需要跑一次最短路就可求出相应的 \(d_i\)。

与差分约束问题相同，当存在一组解 \(\{a_1,a_2,\cdots,a_n\}\) 时，\(\{a_1+d,a_2+d,\cdots,a_n+d\}\) 同样为一组解，因此在该题让 \(i=1\) 作为源点，此时源点处的 \(dis_{1}=1\) 在已知范围内最小，因此得到的也是一组最小的解。

答案即为：

\[ \sum_{i=0}^{x-1}\left(\frac{h-d_i}{x} + 1\right) \]

加 1 是由于 \(d_i\) 所在楼层也算一次。

代码实现上注意到 \(h\) 的范围是 \(h \leq 2^{63}-1\)，所以在求解最短路之前 \(d_i\) 的初始值应至少设为 \(2^{63}\)，这超过了 C++ 中 long long 的最大值。所以可以使用 unsigned long long 或者先把 \(h \gets h - 1\)，然后把最低楼层设为 \(0\) 层，其他代码无异。

参考实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <queue>

using namespace std;
using ll = long long;
constexpr int MAXN = 100010;
constexpr ll linf = (1ull << 63) - 1;

ll h, x, y, z;
ll head[MAXN << 1], tot;
ll dis[MAXN], vis[MAXN];
queue<int> q;

struct edge {
  ll to, next, w;
} e[MAXN << 1];

void add(ll u, ll v, ll w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void spfa() {  // spfa算法，可看最短路部分
  dis[0] = 0;
  vis[0] = 1;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> h;
  cin >> x >> y >> z;
  if (x == 1 || y == 1 || z == 1) {
    cout << h << '\n';
    return 0;
  }
  --h;
  for (int i = 0; i < x; i++) {
    add(i, (i + z) % x, z);
    add(i, (i + y) % x, y);
    dis[i] = linf;
  }
  spfa();
  ll ans = 0;
  for (int i = 0; i < x; i++) {
    if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
  }
  cout << ans << '\n';
  return 0;
}

例题二

ARC084B Small Multiple

题目大意：给定 \(n\)，求 \(n\) 的倍数中，数位和最小的那一个的数位和。（\(1\le n\le 10^5\)）

本题可以使用循环卷积优化完全背包在 \(O(n\log^2 n)\) 的时间内解决，但我们希望得到线性的算法。

观察到任意一个正整数都可以从 \(1\) 开始，按照某种顺序执行乘 \(10\)、加 \(1\) 的操作，最终得到，而其中加 \(1\) 操作的次数就是这个数的数位和。这提示我们使用最短路。

对于所有 \(0\le k\le n-1\)，从 \(k\) 向 \(10k\) 连边权为 \(0\) 的边；从 \(k\) 向 \(k+1\) 连边权为 \(1\) 的边。（点的编号均在模 \(n\) 意义下）

每个 \(n\) 的倍数在这个图中都对应了 \(1\) 号点到 \(0\) 号点的一条路径，求出 \(1\) 到 \(0\) 的最短路即可。某些路径不合法（如连续走了 \(10\) 条边权为 \(1\) 的边），但这些路径产生的答案一定不优，不影响答案。

时间复杂度 \(O(n)\)。

习题

洛谷 P3403 跳楼机

洛谷 P2662 牛场围栏

[国家集训队] 墨墨的等式

「NOIP2018」货币系统

AGC057D - Sum Avoidance

「THUPC 2023 初赛」背包

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用