Description
Link：CF2178H
有三种类型的礼物，价值分别为 a,b,c。初始时，恰好拥有每一种礼物各一份。
给出两个整数 m 与 k。你可以进行若干次操作，每次操作形如以下的两种：
- 创造：选择一种礼物类型，并额外制作一份该类型的礼物。消耗 x 点法力值，其中 x∈{a,b,c} 为所选礼物类型的价值。
- 复制：选择一种礼物类型，并复制该类型的所有礼物。消耗 k 点法力值。
你需要求出，使得礼物价值总和是 m 的倍数时，所需的最小法力值。
数据范围：1≤a<b<c<m≤5×105，1≤k≤5×105，1≤∑m,∑k≤5×105。
时空限制：6s / 1024MiB。
Solution
首先三种类型的礼物是独立的。对于每种礼物而言，问题就转化为了简单的“同余最短路”。但由于 (min,+) 卷积只能做到 O(n2)，所以分开求解答案再合并的思路不太能做。
为什么不能只记录总价值 mod m 作为状态？因为三种礼物混在一起，虽然创造操作仍然可以进行，但是复制操作我们就不知道如何更新状态了。
因此考虑挖掘操作的性质。注意到代价分别为 k 的复制 a×2,b×2，相当于代价为 2k 的复制 (a+b)×2。这启发我们，可以将复制操作捆绑在一起进行（而不是分开考虑它们）。
然而，由于初始时每个礼物各有一个，有时我们不希望复制某个元素。所以我们可以视作初态手上没有任何礼物，终态每个礼物必须被创造过（并且在最终的价值中减去 a+b+c）。
设状态 (mask,x) 表示当前已经创造礼物构成的二进制状态为 mask，礼物总价值 mod m 等于 x 的情况。则我们有如下转移：
- (mask,x)→(mask∣100,(x+a)modm)，代价为 a。
- (mask,x)→(mask∣010,(x+b)modm)，代价为 b。
- (mask,x)→(mask∣001,(x+c)modm)，代价为 c。
- (mask,x)→(mask,2xmodm)，代价为 ∣mask∣⋅k。
可以证明，任何一种操作序列，都等价于上述的状态转移。简单证明：考虑先忽略所有的创造操作，将所有的复制操作倒序对齐，然后再将其他的创造操作插入进去。
时间复杂度 O(mlogm)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #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;
}
|