[DP-1]【转载】同余最短路的转圈技巧

Moeebius · 2023-09-28 20:36:24 · 题解

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

考虑暴力。记 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;
}