同余最短路

同余最短路还在写最短路？感觉不如转圈！

众所周知，在同余最短路算法中，我们选取一个基准物品的体积作为模数 $m$，并对其它物品的体积 $v_i$ 和所有 $0\leq i < m$，从 $i$ 向 $(i +v_i)\mod m$ 连权值为 $v_i$ 的边，跑最短路。

算法介绍

实际上，存在简单的不需要最短路的做法。

不要从图论的角度考虑问题，而是回归本源：完全背包。更具体地，体积模 $m$ 意义下的完全背包。对于体积为 $v_i$ 的物品，它在长度为 $m$ 的环上形成 $d=gcd(v_i,m)$ 个子环。从一个点出发，不可能绕着子环走一圈再转移回到该点，因为最短路不会经过同一个点两次，否则存在负环。另一种理解方式是，如果绕着环走了一圈，相当于选择了 $\frac m d$ 个体积为 $v_i$ 的物品，而这些物品可以替换为若干基准物品而被忽略，使得总体积更小。进一步地，如果重复经过同一个点，那么可以将这两次经过之间加入的所有物品替换为若干基准物品。

因此，往背包加入体积为 $v_i$ 的物品时，至多加入 $\frac{m}{\gcd(v_i,m)}-1$ 个。对于每一个子环，我们绕着这个环转两圈，即可考虑到所有转移，因为每个点都转移到了子环上的其它所有点。时间复杂度 $\mathcal{O}(nm)$。

for(int i = 0, lim = __gcd(v[i], m); i < lim; i++)
  for(int j = i, c = 0; c < 2; c += j == i) {
    int p = (j + v[i]) % m;
    f[p] = min(f[p], f[j] + v[i]), j = p;
  }

对于普通的完全背包，即边权等于 $v_i$ 的问题，我们找到子环上权值最小的点，绕着环转移一圈即可,但是写起来不如转两圈简洁。

例题

P2371 墨墨的等式

以下是经典题墨墨的等式的转圈代码。它是普通的完全背包。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, 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];
  memset(f, 0x3f, sizeof(f)), f[0] = 0;
  sort(a + 1, a + n + 1), m = a[1];
  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]) % 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$ ，那么我们同样不会经过同一个点，原因是类似的：因为 $\frac{c_i}{v_i} \leq \frac w m$，所以如果若干其它物品可以替换为若干基准物品，我们一定会这么做，以最大化单位体积贡献的价值。

但是，对于两组背包方案 $(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}$的限制保证了正确性。