「CF2178H」Create or Duplicate

    「CF2178H」Create or Duplicate

    CF2178H

    有三种类型的礼物,价值分别为 a,b,ca, b, c。初始时,恰好拥有每一种礼物各一份。

    给出两个整数 mm 与 kk。你可以进行若干次操作,每次操作形如以下的两种:

    • 创造:选择一种礼物类型,并额外制作一份该类型的礼物。消耗 xx 点法力值,其中 x∈{a,b,c}x \in \{ a, b, c \} 为所选礼物类型的价值。
    • 复制:选择一种礼物类型,并复制该类型的所有礼物。消耗 kk 点法力值。

    你需要求出,使得礼物价值总和是 mm 的倍数时,所需的最小法力值。

    数据范围:1≤a<b<c<m≤5×1051 \leq a < b < c < m \leq 5 \times 10^5,1≤k≤5×1051 \leq k \leq 5 \times 10^5,1≤∑m,∑k≤5×1051 \leq \sum m, \sum k \leq 5 \times 10^5。

    时空限制:66s / 10241024MiB。

    Solution

    首先三种类型的礼物是独立的。对于每种礼物而言,问题就转化为了简单的“同余最短路”。但由于 (min⁡,+)(\min, +) 卷积只能做到 O(n2)\mathcal{O}(n^2),所以分开求解答案再合并的思路不太能做。

    为什么不能只记录总价值  mod  m\bmod \ m 作为状态?因为三种礼物混在一起,虽然创造操作仍然可以进行,但是复制操作我们就不知道如何更新状态了。

    因此考虑挖掘操作的性质。注意到代价分别为 kk 的复制 a×2,b×2a\times 2, b\times 2,相当于代价为 2k2k 的复制 (a+b)×2(a + b) \times 2。这启发我们,可以将复制操作捆绑在一起进行(而不是分开考虑它们)。

    然而,由于初始时每个礼物各有一个,有时我们不希望复制某个元素。所以我们可以视作初态手上没有任何礼物,终态每个礼物必须被创造过(并且在最终的价值中减去 a+b+ca + b + c)。

    设状态 (mask,x)(\mathrm{mask}, x) 表示当前已经创造礼物构成的二进制状态为 mask\mathrm{mask},礼物总价值  mod  m\bmod \ m 等于 xx 的情况。则我们有如下转移:

    • (mask,x)→(mask∣100,(x+a) mod m)(\mathrm{mask}, x) \to (\mathrm{mask} \mid \mathtt{100}, (x + a) \bmod m),代价为 aa。
    • (mask,x)→(mask∣010,(x+b) mod m)(\mathrm{mask}, x) \to (\mathrm{mask} \mid \mathtt{010}, (x + b) \bmod m),代价为 bb。
    • (mask,x)→(mask∣001,(x+c) mod m)(\mathrm{mask}, x) \to (\mathrm{mask} \mid \mathtt{001}, (x + c) \bmod m),代价为 cc。
    • (mask,x)→(mask,2x mod m)(\mathrm{mask}, x) \to (\mathrm{mask}, 2x \bmod m),代价为 ∣mask∣⋅k|\mathrm{mask}| \cdot k。

    可以证明,任何一种操作序列,都等价于上述的状态转移。简单证明:考虑先忽略所有的创造操作,将所有的复制操作倒序对齐,然后再将其他的创造操作插入进去。

    时间复杂度 O(mlog⁡m)\mathcal{O}(m \log m)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 500100;
    const i64 inf = 1e18;
    
    int a, b, c, m, k;
    
    i64 d[8][N];
    int vis[8][N];
    
    void work() {
        std::cin >> a >> b >> c >> m >> k;
    
        for (int mask = 0; mask < 8; mask ++) {
            for (int i = 0; i < m; i ++) {
                d[mask][i] = inf, vis[mask][i] = 0;
            }
        }
        d[0][0] = 0;
    
        std::priority_queue< std::tuple<i64, int, int> > q;
        q.push({0, 0, 0});
    
        while (q.size()) {
            auto [_, h, x] = q.top(); q.pop();
    
            if (vis[h][x]) {
                continue;
            }
            vis[h][x] = 1;
    
            auto extend = [&] (int nh, int nx, int w) {
                if (d[h][x] + w < d[nh][nx]) {
                    d[nh][nx] = d[h][x] + w;
                    q.push({-d[nh][nx], nh, nx});
                }
            };
    
            extend(h | (1 << 0), (x + a) % m, a);
            extend(h | (1 << 1), (x + b) % m, b);
            extend(h | (1 << 2), (x + c) % m, c);
            extend(h, 2 * x % m, __builtin_popcount(h) * k);
        }
    
        i64 ans = d[7][0] - a - b - c;
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }