跳转至

同余最短路径⚓︎

同余最短路径问题是一类在图论中涉及路径长度满足特定模数条件的最短路径问题。具体来说，给定一个带权有向图和一个整数模数 k，希望找到从起点到终点的最短路径，使得路径长度对 k 取模后满足某个特定的条件（例如等于某个值）。

同余最短路径适用于边权非负的情况，一般用于解决如下问题：

  1. 给定 n 个整数，求这 n 个整数能拼凑出多少的其他整数（n 个整数可以重复取）
  2. 给定 n 个整数，求这 n 个整数不能拼凑出的最小（最大）的整数
  3. 给定 n 个整数，求这 n 个整数拼凑出模 K 余 p 的数的最小（最大）次数
  4. 总体积极大，单个物品体积较小，这一类完全背包问题（同余分组）

单源最短路⚓︎

解决同余最短路的一种方法是将图中的每个节点扩展为 K 个状态节点，表示路径长度对 K 取模后的不同余数。然后在这个扩展后的图上运行标准的最短路径算法（如 \text{Dijkstra} 或 \text{Bellman-Ford}），以找到满足条件的最短路径。

具体如下：

  1. 构造图的节点为 [0, K-1]，表示当前数对 K 取模的结果
  2. 对于每个节点 u，枚举 n 个整数 a_i，构造一条从 u 到 v 的边，其中 v = (u + a_i) \bmod K，边权为 a_i
  3. 从节点 0 出发，使用 \text{Dijkstra} (如果边权都是 0,1 可以使用 \text{0-1 BFS}) 求解最短路

利用同余构造的这些状态可以看作单源最短路中的点。状态转移如下:

f(i + y) = f(i) + y，类似单源最短路中 f(v) = f(u) + edge(u, v)

跳楼机

给定三个正整数 x, y, z 和一个非负整数 h，求使用 x, y, z 这三个数（可以重复使用）拼凑出不超过 h 的所有正整数的个数。

数据范围

1 \leq h \leq 2^{63}-1，在求解最短路时初始值应该至少设置成 2^{63}，但是这个数已经超出了 int64_t 的范围。

可以将 h 减 1，从 0 开始计数，也不影响结果。或者使用uint64_t类型。

C++
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int64_t dijkstra(uint64_t x, uint64_t y, uint64_t z, uint64_t h) {
  uint64_t k = min({x, y, z});
  vector<uint64_t> distance(k, UINT64_MAX);
  distance[1] = 1;  // 从 1 开始计数
  // Dijkstra
  using PII = pair<uint64_t, uint64_t>;
  priority_queue<PII, vector<PII>, greater<>> pq;  // {dist, node}
  pq.emplace(1, 1);
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    pq.pop();
    if (dist > distance[u]) { continue; }
    for (auto edge : {x, y, z}) {  // 枚举每条边, 避免建图
      uint64_t v = (u + edge) % k;
      if (distance[u] + edge < distance[v]) {
        distance[v] = distance[u] + edge;
        pq.emplace(distance[v], v);
      }
    }
  }

  int64_t result = 0;
  for (int64_t i = 0; i < k; ++i) {
    if (distance[i] <= h) { result += (h - distance[i]) / k + 1; }
  }
  return result;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  uint64_t h, x, y, z;
  cin >> h >> x >> y >> z;
  if (x == 1 || y == 1 || z == 1) {  // 有 1 可以拼凑出所有数
    cout << h << "\n";
    return 0;
  }
  cout << dijkstra(x, y, z, h) << "\n";
  return 0;
}

两次转圈法⚓︎

解决同余最短路问题的另一种方法是使用两次转圈法。具体步骤如下：

  1. 给定一个基准数 x，那么可能的余数为 [0, x-1]
  2. 假设当前余数是 cur，当前出现数字为 y，(cur + y) \bmod x 是出现的新余数，最终会回到 cur
  3. 当前出现数字为 y，[0, x-1] 这些点，会形成 \gcd(x,y) 个子环，所有子环的起点为：[0, \gcd(x,y)-1]
  4. 每个子环的长度为 x/\gcd(x,y)
  5. 因为是最短路，所以每出现一个新的数字 y，所形成的每个子环，只需要转一圈即可完成更新

特别注意

子环的起点不一定是点权最小的点，所以实现中往往用转两圈的方式。

墨墨的等式

给定 n 个整数 a_1, a_2, \ldots, a_n，求 \sum a_i \cdot b_i = b \in [l, r]，在 [l, r] 范围内有多少个数可以被表示。a_i 为正整数，b_i 为非负整数。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int64_t two_loop(const vector<int64_t> &a, int64_t l, int64_t r) {
  int64_t k = *min_element(a.begin(), a.end());  // 基准数
  vector<int64_t> distance(k, INT64_MAX);
  distance[0] = 0;    // 从0开始计数
  for (auto x : a) {  // 枚举每个物品
    int64_t g    = gcd(k, x);
    int64_t step = k / g;
    for (int64_t start = 0; start < g; ++start) {  // 枚举每个子环的起点
      for (int64_t t = 0; t < 2 * step; ++t) {     // 转两圈
        int64_t u = (start + t * x) % k;
        int64_t v = (u + x) % k;
        if (distance[u] != INT64_MAX && distance[u] + x < distance[v]) {
          distance[v] = distance[u] + x;
        }
      }
    }
  }

  int64_t result = 0;
  for (int64_t i = 0; i < k; ++i) {  // 枚举每个模, 计算能表示的数字个数
    if (distance[i] <= r) { result += (r - distance[i]) / k + 1; }
    if (distance[i] <= l - 1) { result -= (l - 1 - distance[i]) / k + 1; }
  }
  return result;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, l, r;
  cin >> n >> l >> r;
  vector<int64_t> a(n);
  int64_t j = 0;
  for (int64_t i = 0; i < n; ++i) {
    cin >> a[j];
    if (a[j] == 0) { continue; }  // 0 不影响方程的解
    j++;
  }
  a.resize(j);

  cout << two_loop(a, l, r) << "\n";
  return 0;
}

评论