Luogu

眾所周知，在同余最短路算法中，我們選取基準物品的體積作為模數 \(m\)，并對其它物品的體積 \(v_i\) 和所有 \(0\leq j < m\)，從 \(j\) 向 \((j + v_i)\bmod m\) 連權值為 \(v_i\) 的邊，跑最短路。

算法介紹

不要從圖論的角度考慮問題，而是回歸本源：體積模 \(m\) 意義下的完全背包。對于體積為 \(v_i\) 的物品，它在長度為 \(m\) 的環上形成 \(d = \gcd(v_i, m)\) 個子環。從一個點出發，不可能繞著子環走一圈再轉移回到該點，因為最短路不會經過同一個點兩次，否則存在負環。如果重復經過同一個點，那么可以將這兩次經過之間加入的所有物品替換為若干基準物品。

因此，往背包加入體積為 \(v_i\) 的物品時，至多加入 \(\frac {m} {\gcd(v_i, m)} - 1\) 個。對于每一個子環，我們繞著這個環轉兩圈，即可考慮到所有轉移，因為每個點都轉移到了子環上其它所有點。時間復雜度 \(\mathcal{O}(nm)\)。

對于普通的完全背包，即邊權等于 \(v_i\) 的問題，我們找到子環上權值最小的點，繞著環轉移一圈即可（daklqw）。但是寫起來不如轉兩圈簡潔。

例題

P2371 墨墨的等式

以下是經典同余最短路問題「墨墨的等式」的轉圈代碼。它是普通的完全背包。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, m, a[N], _a[N];
long long f[N], l, r, ans;
int main() {
  cin >> n >> l >> r;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    if(!a[i]) n--, i--;
  }
  if(!n) cout << "0\n", exit(0);
  memset(f, 0x3f, sizeof(f)), f[0] = 0;
  sort(a + 1, a + n + 1), m = a[1];
  for(int i = 1; i <= n; i++) _a[i] = a[i] % m; // 避免多次取模常數太大
  for(int i = 2; i <= n; i++) {
    for(int j = 0, lim = __gcd(a[i], m); j < lim; j++) {
      for(int t = j, c = 0; c < 2; c += t == j) {
        int p = t + _a[i];
        if(p >= m) p -= m;
        f[p] = min(f[p], f[t] + a[i]), t = p;
      }
    }
  }
  for(int i = 0; i < a[1]; i++) {
    if(r >= f[i]) ans += max(0ll, (r - f[i]) / a[1] + 1);
    if(l > f[i]) ans -= max(0ll, (l - 1 - f[i]) / a[1] + 1);
  }
  cout << ans << endl;
  return 0;
}

P9140 背包

本題在完全背包的可行性基礎上加入了權值這一維度。

如果我們將 \(\frac {c_i}{v_i}\) 最大的物品選做基準物品，設其體積為 \(m\)，價值為 \(w\)，那么同樣不會經過同一個點，原因是類似的：將一部分其它物品替換為若干基準物品，以最大化單位體積貢獻的價值。

對于兩組背包方案 \((V_1, C_1)\) 和 \((V_2, C_2)\)，若 \(V_1\equiv V_2\pmod m\)，該如何衡量這兩組方案的優劣呢？

對于一組背包方案 \((V', C')\) 和一次查詢 \(V\)，若 \(V'\equiv V\pmod m\) 且 \(V' \leq V\)，則其權值為 \(C' + \frac {V - V'} mw\)。因此，對于相同剩余系的所有背包方案 \((V', C')\)，我們希望最大化 \(C' - \lfloor\frac {V'} {m}\rfloor w\)，轉化為圖論就是最長路的 \(dist\)。也就是說，當加入物品 \((v_i, c_i)\) 從 \(p\) 轉移到 \(q = (p + v_i)\bmod m\) 時，用于更新 \(f_q\) 的值為 \(f_p + c_i - \lfloor \frac {p + v_i} {m}\rfloor w\)。

根據 \(\frac {w} {m}\) 的最大性，這樣一張包含正負權邊的圖上不存在正權環（求最長路）。又因為不經過重復點，所以每組剩余系的最優方案對應的 \(V'\) 不超過 \(m ^ 2\) 即 \(10 ^ {10}\)，配合 \(V\geq 10 ^ {11}\) 的限制保證了正確性。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
ll n, q, m = 1, w, V, f[N], c[55], v[55], _v[55], _d[55];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for(int i = 1; i <= n; i++) {
    cin >> v[i] >> c[i];
    if(w * v[i] < m * c[i]) w = c[i], m = v[i];
  }
  for(int i = 1; i <= n; i++) _v[i] = v[i] % m, _d[i] = v[i] / m; // 避免多次取模和除法常數太大
  for(int i = 1; i < m; i++) f[i] = -1e18;
  for(int i = 1; i <= n; i++) {
    for(int j = 0, lim = __gcd(v[i], m); j < lim; j++) {
      for(int t = j, _ = 0; _ < 2; _ += t == j) {
        int q = t + _v[i], d = _d[i];
        if(q >= m) q -= m, d++;
        f[q] = max(f[q], f[t] + c[i] - d * w), t = q;
      }
    }
  }
  for(int i = 1; i <= q; i++) {
    cin >> V;
    int p = V % m;
    if(f[p] < -1e17) cout << "-1\n";
    else cout << f[p] + V / m * w << "\n";
  }
  return 0;
}

和其它算法的對比

SPFA 跑同余最短路的復雜度依然是個謎。它的理論上界是 \(\mathcal{O}(|V||E|)\) 即 \(\mathcal{O}(nm ^ 2)\)，但實際表現和小常數 \(\mathcal{O}(nm)\) 同樣優秀。

此外，在可以使用最大體積作為基準元素時，令 \(f_i\) 除以 \(m\) 下取整得 \(f'_i\)，則 \(f_i = f'_i m + i\)。對于 \(f'\)，邊權只有 \(0\) 或 \(1\)，01-BFS（FZzzz）。

顯然，轉圈技巧比最短路好寫，且適用范圍沒有任何限制，如 01-BFS 就無法解決第二道例題。

總結

同余最短路的本質是根據單調性值域定義域互換后將完全背包轉化為體積模 \(m\) 意義下的完全背包。普通完全背包的轉移是有向無環圖，而體積模 \(m\) 的完全背包的轉移成環，這讓我們想到最短路。最短路不成環，對應原問題就是可以將兩次經過同一個點之間添加的所有物品換成若干基準物品。所以，我們可以將完全背包轉化為類多重背包問題。

筆者在研究「背包」一題的官方解法時，驚訝于其 “轉兩圈” 思想的巧妙。翻了一遍經典同余最短路題目，也沒找到幾篇除了 SPFA 和 Dijkstra 以外的題解，故分享給各位讀者。

同余最短路還在寫最短路？時代的眼淚！