同餘最短路

當出現形如「給定 \(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\) 所在樓層也算一次。

參考實現

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;

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[1] = 1;
  vis[1] = 1;
  q.push(1);
  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() {
  memset(dis, INF, sizeof(dis));
  scanf("%lld", &h);
  scanf("%lld %lld %lld", &x, &y, &z);
  if (x == 1 || y == 1 || z == 1) {
    printf("%lld\n", h);
    return 0;
  }
  for (int i = 0; i < x; i++) {
    add(i, (i + z) % x, z);
    add(i, (i + y) % x, y);
  }
  spfa();
  ll ans = 0;
  for (int i = 0; i < x; i++) {
    if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
  }
  printf("%lld\n", ans);
  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)\)。

習題

AGC057D - Sum Avoidance

「THUPC 2023 初賽」揹包

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