Đường đi ngắn nhất trên đồ thị module

Khi gặp các bài toán dạng như "Cho \(n\) số nguyên, hỏi có thể ghép được bao nhiêu số nguyên khác từ \(n\) số này (mỗi số có thể lấy nhiều lần)", hoặc "Cho \(n\) số nguyên, hỏi số nguyên nhỏ nhất (lớn nhất) không thể ghép được từ \(n\) số này", hoặc "Ít nhất cần ghép mấy lần để được số có phần dư \(p\) khi chia cho \(K\)" thì có thể sử dụng phương pháp "đường đi ngắn nhất theo đồng dư" (modulo shortest path).

Phương pháp này tận dụng việc xây dựng trạng thái dựa trên đồng dư để tối ưu hóa độ phức tạp không gian.

Tương tự như ràng buộc hiệu (difference constraints), các trạng thái xây dựng dựa trên đồng dư có thể coi như các đỉnh trong bài toán đường đi ngắn nhất một nguồn. Chuyển trạng thái thường có dạng \(f(i+y) = f(i) + y\), tương tự như trong đường đi ngắn nhất \(f(v) = f(u) +edge(u,v)\).

Bài toán mẫu

Ví dụ 1

P3403 Thang máy nhảy tầng

Đề bài: Cho \(x, y, z, h\), với mỗi \(k \in [1,h]\), có bao nhiêu \(k\) thỏa mãn \(ax+by+cz=k\) (\(0\leq a,b,c\), \(1\le x,y,z\le 10^5\), \(h\le 2^{63}-1\)).

Giả sử \(x < y < z\).

Gọi \(d_i\) là tầng thấp nhất \(p\) có \(p \bmod x = i\) chỉ sử dụng phép cộng \(y\) và phép cộng \(z\) (tức là chỉ dùng thao tác 2 và 3), tức là số nhỏ nhất đồng dư \(i\) modulo \(x\) có thể đạt được bằng các thao tác này, dùng để tính số lượng số thỏa mãn trong mỗi lớp đồng dư.

Có hai trạng thái chuyển:

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

Thông thường, ta chọn số nhỏ nhất trong dãy \(a_i\) để làm modulo (ở đây là \(x\)) nhằm giảm số trạng thái cần xét (hệ dư nhỏ nhất).

Thực chất, thao tác này tương đương với việc xây dựng cạnh trong bài toán đường đi ngắn nhất:

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

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

Tiếp theo, chỉ cần tính \(d_0, d_1, d_2, \dots, d_{x-1}\), tức là chạy một lần thuật toán đường đi ngắn nhất là đủ.

Cài đặt dựa trên đường đi ngắn nhất

#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;
}

Tuy nhiên, thực tế không cần chạy thuật toán đường đi ngắn nhất thông thường, vì có hai tính chất đặc biệt:

Thứ nhất, chỉ có hai loại trọng số cạnh, và với mỗi đường đi, do tính chất giao hoán của phép cộng, thứ tự đi các loại cạnh không ảnh hưởng kết quả. Do đó, có thể thực hiện hai lần đường đi ngắn nhất, mỗi lần chỉ xây dựng một loại cạnh.

Thứ hai, với đồ thị chỉ có một loại trọng số, mỗi đỉnh \(u\) có một cạnh vào (từ \((u-y) \bmod x\)) và một cạnh ra (tới \((u+y) \bmod x\)), nên toàn bộ đồ thị là hợp của một số vòng. Có thể chứng minh có đúng \(\gcd(x, y)\) vòng, mỗi vòng có độ dài bằng nhau.

Chứng minh

Gọi \(d=\gcd(x,y)\), \(x=da, y=db\), với \(\gcd(a,b)=1\).

Xét đi từ \(u\) qua \(k\) bước, đến \((u+ky) \bmod x\). Nếu tạo thành vòng, thì \(ky \equiv 0 \pmod x\), tức là \(kb \equiv 0 \pmod a\).

Do \(\gcd(a,b)=1\), giá trị nhỏ nhất của \(k\) là \(a\), tức là độ dài vòng là \(a = \dfrac{x}{d}\). Vì có thể bắt đầu từ bất kỳ đỉnh nào, nên số vòng là \(d\).

Hơn nữa, trọng số cạnh dương, nên sau hai vòng chắc chắn không thể tiếp tục nới lỏng. Chỉ cần cập nhật một vòng là đủ. Nhờ đó, độ phức tạp không bị giới hạn bởi thuật toán đường đi ngắn nhất, có thể đạt \(O(x)\).

Tương tự như bài toán ràng buộc hiệu, nếu tồn tại một bộ nghiệm \(\{a_1,a_2,\cdots,a_n\}\) thì \(\{a_1+d,a_2+d,\cdots,a_n+d\}\) cũng là nghiệm. Do đó, chọn \(i=1\) làm đỉnh nguồn, khi đó \(dis_{1}=1\) là nhỏ nhất trong phạm vi đã biết, nên nghiệm thu được cũng là nhỏ nhất.

Đáp án là:

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

Cộng thêm 1 vì tầng \(d_i\) cũng được tính.

Lưu ý: \(h\) có thể rất lớn (\(h \leq 2^{63}-1\)), nên trước khi chạy đường đi ngắn nhất, giá trị khởi tạo của \(d_i\) phải ít nhất là \(2^{63}\), vượt quá giá trị lớn nhất của long long trong C++. Có thể dùng unsigned long long hoặc giảm \(h \gets h - 1\), đặt tầng thấp nhất là \(0\), các phần còn lại không đổi.

Cài đặt tối ưu dựa trên vòng

#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) {
          // 如果d[las]=LLONG_MAX，d[las]+step会越界，需要特判
          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;
    // 本题的h达到了ll的上界，如果使用ll的话必需把初值置为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;
}

Ví dụ 2

ARC084B Small Multiple

Đề bài: Cho \(n\), tìm số nhỏ nhất là bội của \(n\) có tổng các chữ số nhỏ nhất. (\(1\le n\le 10^5\))

Bài này có thể dùng tích chập tuần hoàn để tối ưu bài toán ba lô đầy đủ trong \(O(n\log^2 n)\), nhưng ta mong muốn thuật toán tuyến tính.

Nhận thấy mọi số nguyên dương đều có thể bắt đầu từ \(1\), thực hiện một chuỗi thao tác nhân \(10\) và cộng \(1\) để thu được, trong đó số lần cộng \(1\) chính là tổng các chữ số. Điều này gợi ý sử dụng đường đi ngắn nhất.

Với mọi \(0\le k\le n-1\), từ \(k\) nối cạnh trọng số \(0\) tới \(10k\); từ \(k\) nối cạnh trọng số \(1\) tới \(k+1\) (tất cả tính theo modulo \(n\)).

Mỗi bội của \(n\) tương ứng với một đường đi từ đỉnh \(1\) tới đỉnh \(0\) trên đồ thị này, tìm đường đi ngắn nhất từ \(1\) tới \(0\) là đáp án. Một số đường đi không hợp lệ (ví dụ đi liên tiếp \(10\) cạnh trọng số \(1\)), nhưng các đường đi này không cho đáp án tốt hơn nên không ảnh hưởng kết quả.

Độ phức tạp \(O(n)\).

Bài tập

洛谷 P3403 Thang máy nhảy tầng

洛谷 P2662 Hàng rào chuồng bò

[Đội tuyển quốc gia] Phương trình của Momo

「NOIP2018」Hệ thống tiền tệ

AGC057D - Sum Avoidance

「THUPC 2023 Sơ khảo」Ba lô

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply