Shortest Path Modulo

When encountering problems of the form "Given \(n\) integers, how many other integers can be formed by summing these \(n\) integers (each integer can be used repeatedly)", or "Given \(n\) integers, find the smallest (largest) integer that cannot be formed", or "What is the minimum number of items needed to form a sum congruent to \(p\) modulo \(K\)", the method of congruence shortest path can be used.

Congruence shortest path uses congruence to construct certain states, which can optimize space complexity.

Analogous to the difference constraints method, the states constructed using congruence can be viewed as vertices in a single-source shortest path problem. The state transitions in congruence shortest path are typically of the form \(f(i+y) = f(i) + y\), similar to \(f(v) = f(u) + edge(u,v)\) in single-source shortest path.

Examples

Example 1

P3403 Jump Machine

Problem summary: Given \(x, y, z, h\), for \(k \in [1,h]\), how many \(k\) satisfy \(ax+by+cz=k\)? (\(0\leq a,b,c\), \(1\le x,y,z\le 10^5\), \(h\le 2^{63}-1\))

Assume without loss of generality that \(x < y < z\).

Let \(d_i\) be the lowest floor \(p\) reachable using only Operation 2 and Operation 3, such that \(p\bmod x = i\). That is, the smallest number congruent to \(i\) modulo \(x\) obtainable after applying Operation 2 and Operation 3, used to count the number of valid numbers in this residue class.

We obtain two state transitions:

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

Note: Usually, we take the modulus with the smallest number among the given set \(a_i\), which is \(x\) here, to minimize space complexity (smallest residue system).

This essentially corresponds to constructing edges in a shortest path graph:

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

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

Next, we only need to compute \(d_0, d_1, d_2, \dots, d_{x-1}\), which can be obtained by running a single shortest path algorithm.

Implementation based on shortest path

#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 algorithm, refer to the shortest path section
  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;
}

However, a normal shortest path computation is not strictly necessary. Note two special properties:

First, there are only two edge weights, and for any path, due to the commutativity of addition, the order of taking edges of different weights does not matter. Therefore, we can consider performing two shortest path passes, each time only constructing edges of one weight type.

Second, for a graph with only one type of edge weight, each vertex \(u\) has exactly one incoming edge (from \((u-y) \bmod x\)) and one outgoing edge (to \((u+y) \bmod x\)). Thus, the entire graph must consist of several cycles. Moreover, it can be proven that there are exactly \(\gcd(x,y)\) cycles of equal length.

Proof

Let \(d=\gcd(x,y)\), and let \(x=da, y=db\), where \(\gcd(a,b)=1\).

Consider starting from \(u\) and taking \(k\) steps, arriving at \((u+ky) \bmod x\). To form a cycle, we require \(ky \equiv 0 \pmod x\), i.e., \(kb \equiv 0 \pmod a\).

Since \(\gcd(a,b)=1\), the smallest \(k\) is \(a\), meaning the cycle length is \(a = \dfrac{x}{d}\). Since we can start from any vertex, all possible cycles have the same length, and the number of cycles is \(d\).

Furthermore, since edge weights are positive, after traversing a cycle twice, no further relaxation is possible. We can directly update by looping through each cycle once. This approach avoids the complexity limitations of general shortest path algorithms and achieves \(O(x)\).

Similar to difference constraint problems, when a solution set \(\{a_1,a_2,\cdots,a_n\}\) exists, \(\{a_1+d,a_2+d,\cdots,a_n+d\}\) is also a solution set. Therefore, in this problem, we set \(i=1\) as the source vertex. At this source, \(dis_{1}=1\) is the minimum within the known range, so the obtained solution is also a set of minimal values.

The answer is:

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

The \(+1\) is because the floor corresponding to \(d_i\) itself is also counted.

In code implementation, note that \(h\) can be as large as \(h \leq 2^{63}-1\). Therefore, before running the shortest path, the initial value for \(d_i\) should be at least \(2^{63}\), which exceeds the maximum value of long long in C++. We can use unsigned long long, or first set \(h \gets h - 1\), then set the lowest floor to \(0\), with the rest of the code unchanged.

Implementation based on cycle optimization

#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <vector>

using ll = long long;

constexpr int maxn = 1e5 + 100;

ll d[maxn];
bool vis[maxn];
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void upd(int step, int M) {
  int D = gcd(step, M);
  int len = M / D;

  for (int st = 0; st < D; st++) {
    if (vis[st]) continue;
    std::vector<int> v;
    int u = st;
    for (int i = 0; i < len; i++) {
      v.push_back(u);
      vis[u] = true;
      u = (u + step) % M;
    }
    for (int r = 0; r < 2; r++) {
      for (int i = 0; i < len; i++) {
        int las = v[i];
        int now = v[(i + 1) % len];
        if (d[las] != LLONG_MAX) {
          // If d[las] = LLONG_MAX, d[las] + step will overflow, special handling is needed.
          d[now] = std::min(d[now], d[las] + step);
        }
      }
    }
  }
}

int main() {
  ll h;
  std::cin >> h;
  int x[3];
  for (int i = 0; i < 3; i++) {
    std::cin >> x[i];
  }
  std::sort(x, x + 3);
  int M = x[0];

  for (int i = 0; i < M; i++) {
    d[i] = LLONG_MAX;
    // The value of h in this problem reaches the upper bound of ll, so if using ll, the initial value must be set to LLONG_MAX.
  }
  d[0] = 0;

  upd(x[1], M);
  memset(vis, 0, sizeof(vis));
  upd(x[2], M);

  ll H = h - 1;
  ans = 0;
  for (int i = 0; i < M; i++) {
    if (d[i] <= H && d[i] != LLONG_MAX) {
      ans += (H - d[i]) / M + 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Example 2

ARC084B Small Multiple

Problem summary: Given \(n\), find the minimum digit sum among multiples of \(n\). (\(1\le n\le 10^5\))

This problem can be solved in \(O(n\log^2 n)\) time using cyclic convolution to optimize the unbounded knapsack, but we aim for a linear algorithm.

Observe that any positive integer can be obtained starting from \(1\) by performing a sequence of operations: multiply by \(10\) and add \(1\). The number of add \(1\) operations equals the digit sum of the number. This suggests using shortest path.

For all \(0\le k\le n-1\), add an edge from \(k\) to \(10k\) with weight \(0\); add an edge from \(k\) to \(k+1\) with weight \(1\). (All vertex indices are considered modulo \(n\).)

Every multiple of \(n\) corresponds to a path from vertex \(1\) to vertex \(0\) in this graph. Finding the shortest path from \(1\) to \(0\) gives the answer. Some paths may be invalid (e.g., taking \(10\) consecutive weight-\(1\) edges), but they yield suboptimal answers and do not affect the result.

Time complexity is \(O(n)\).

Exercises

Luogu P3403 Jump Machine

Luogu P2662 Cattle Fence

[National Training Team] Momo's Equation

「NOIP2018」Currency System

AGC057D - Sum Avoidance

「THUPC 2023 Preliminary」Knapsack

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