【转载】同余最短路的转圈技巧

鸣谢：魏老师 提供的神仙思路！

考虑暴力。记 $f_i$ 表示 $i$ 这个数能否用题目中的规则表示出来。显然，转移是一个完全背包的形式。

发现题目中 $a_i$ 很小，但值域很大。考虑如下事实：

如果 $f_i = 1$，那么 $\forall j\in a,\ f_{i+j} = 1$。

所以我们并不需要求出所有的 $f_i$！

我们从 $a$ 中选出一个常数，记为 $M$。我们并不用计算出所有 $f_i$，而是令 $g_i=\min\{j\ |\ f_j=1\land j\,\text{mod}\,M=i\}$。这样，$f_i=1$ 的充要条件就是 $g_{i\,\text{mod}\,j}\le j$，并且状态数被优化到了 $O(\max\{a_i\})$。

考虑转移。

暴力的转移即为 $g_{i+a_j} \leftarrow g_i + a_j$。

注意到对于一个状态 $g_i$，转移一圈回到自己一定是不优秀的（因为每次代价非负），并且每个 $a_j$ 转移时形成了 $\gcd(a_j,M)$ 个环。

因此，对于每个 $a_i$，只有可能在这 $\gcd(a_j,M)$ 个环上转移，实现时，我们在每个环上找到最小值，绕着环转一圈即可；或者也可以任取一个起点，绕着环走两圈（因为这样涵盖了从每个点出发的情况）。

计算出 $g$ 数组之后，就可以直接计算答案了！对于 $g_i$，其对 $[0, V]$ 答案的贡献为 $\max\{0,\dfrac{V-g_i}{M} + 1\}$，差分计算即可。

时间复杂度 $O(NM)$。

实现时注意特判 $a_i = 0$ 的情况。

constexpr ll MAXN = 5e5 + 5;
ll n, l, r, f[MAXN];
vector<int> a;
il void solver_main() {
  read(n, l, r);
  For(i, 1, n) {
    int x;
    read(x);
    if (x)
      a.emplace_back(x);
  }
  if (a.empty())
    return puts("0"), void();
  sort(a.begin(), a.end());

  int M = a[0], len = a.size(); // 选取最小值做 M，减小常数
  fill(f, f + M, 1e18 + 5);
  f[0] = 0;
  For(i, 1, len - 1) {
    int lim = __gcd(M, a[i]) - 1; // 环的数量
    For(j, 0, lim) {
      for (int cur = j, cnt = 0; cnt < 2; cnt += cur == j) { // 转两圈
        int nxt = (cur + a[i]) % M;
        f[nxt] = min(f[nxt], f[cur] + a[i]), cur = nxt;
      }
    }
  }

  ll ans = 0;
  For(i, 0, M - 1) {
    if (r >= f[i])
      ans += (r - f[i]) / M + 1;
    if (l > f[i])
      ans -= (l - f[i] - 1) / M + 1;
  }

  cout << ans << endl;
}