题解 P2371 【[国家集训队]墨墨的等式】

· · 题解

一年前写过这道题，然后现在发现了一些奇怪的东西。

首先这道题可以转化为模 A_i 最小值 m 意义下的最短路，求出每个模 m 意义下的值最少要多少代价可以达成，然后分别计算答案的贡献。这个是经典的同余最短路。

实际上，由于同余，边的更新顺序无关——也就是能分层更新。很像循环下标的背包，但是是取min的而不是方案数。

因为顺序无关，考虑单独更新每个权值。因为同余，把 0 \dots m - 1 的所有点按照模 A_i mod m 的值分类，对于点 i 能更新到 j 当且仅当 i \equiv j (mod A_i)，因此，点被划分成了一堆环，环内的分别处理。

对于一个环，容易证明选择距离最小的点开始更新是最优的。因此从最小点开始，维护一个到当前点最小距离，线性扫过去即可。

复杂度 O(nm)

所以为什么那么多人都在写最短路啊……为什么我还跑不过最短路啊……

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 500010;
int n;
LL bmin, bmax, minn, f[MAXN];
int mn, A[MAXN];

int main() {
    std::cin >> n >> bmin >> bmax; --bmin;
    mn = 1234567;
    for (int i = 1; i <= n; ++i)
        std::cin >> A[i], mn = std::min(mn, A[i]);
    memset(f, 0x3f, mn << 3);
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int mod = A[i] % mn;
        if (!mod) continue;
        static bool vis[MAXN];
        memset(vis, 0, mn);
        for (int j = 0; j < mn; ++j) if (!vis[j]) {
            int ma = j, now = j;
            while (!vis[now]) {
                vis[now] = true;
                if (f[now] < f[ma]) ma = now;
                now += mod - mn, now += now >> 31 & mn;
            }
            now = ma;
            LL vn = f[now];
            do {
                f[now] = std::min(f[now], vn);
                vn = std::min(vn, f[now]) + A[i];
                now += mod - mn, now += now >> 31 & mn;
            } while (now != ma);
        }
    }
    LL ans = 0;
    for (int i = 0; i < mn; ++i) {
        ans += f[i] <= bmax ? (bmax - f[i]) / mn + 1 : 0;
        ans -= f[i] <= bmin ? (bmin - f[i]) / mn + 1 : 0;
    }
    std::cout << ans << std::endl;
    return 0;
}