mydcwfy's Blog

CF1103D Professional layer

Posted on
Symbols count in article: 3k Reading time ≈ 6 mins.

题意：给定 $n$ 个数 $a_i$，每个数有一个代价 $c_i$，你可以选择一次集合 $S$，让集合内部的每个数都可以被一个 $\leq k$ 的因数除掉，选择的代价为 $|S|\sum_{i\in S} c_i$。要求使得操作过后 $\gcd_i a_i = 1$ 的最小代价。$n\leq 10 ^ 6$，$a_i\leq 10 ^ {12}$，$c_i\leq 10 ^ 9$。

首先敲一下计算器容易发现 $\gcd_i a_i$ 最多只有 $k = 11$ 个质因数，那么我们对于每个数只需要考虑这些质因数的次数即可。写一个暴力容易发现只考虑 $m = 11$ 个质因数的话只有不超过 $M = 12000$ 个数需要考虑。对于缩减过后相同的数，我们发现只需要保留最小的 $m$ 个即可。这是因为每次选择一个数我们至少需要完全消掉一个质因子，那么只需要保留 $m$ 个即可。

对于一个缩减过后的数，我们枚举质因数集合 $S$，容易判断只选择一个数我们能否将集合 $S$ 全部消掉，这部分是 $O(Mm2 ^ m)$ 的。那么我们相当于对于一个集合 $S$，我们都保留一个最小的代价即可，然后最后直接 $O(m4 ^ m)$ DP 即可。

看似上面的做法没有问题，但是我们注意到对于一个数 $\{a_i, c_i\}$，我们只能选择一次，上面的做法并没有体现出这一点。于是我们考虑同样的对一个集合 $S$，我们只保留前 $m$ 个最小的代价。然后我们将这些可能有用的转移再分到不同的 $\{a_i, c_i\}$，DP 即可。注意最后的代价和 $|S|$ 有关，我们需要记录 $f(i, s)$ 表示选择了 $i$ 个数除，已经将 $s$ 集合的全部消去了的最小 $c$ 和。复杂度是 $O(m ^ 2 4 ^ m)$，可能不太能接受。

考虑我们原来的转移是 $s\to s\cup t$，但是容易发现对于所有的 $t$，他的所有子集的转移同样是被记录的（可能不在有用的转移中，但是肯定是被记录了的）。那么我们可以直接写为 $s\to s + t$，定义为 $s\cap t=\varnothing$。这样的话我们用 $t$ 转移的时候只需要枚举 $U \oplus t$ 的所有子集即可。这样做是 $O(m ^ 23 ^ m)$ 的，是可接受的。

总复杂度 $O(Mm2 ^ m + m ^ 23 ^ m)$，可以通过。

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
int main()
{
	std::cin >> n >> lim;
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	for (int i = 1; i <= n; ++ i) scanf("%d", c + i);
	G = a[1];
	for (int i = 2; i <= n; ++ i) G = Gcd(G, a[i]);
	LL tmp = G;
	for (int i = 2; i <= tmp / i; ++ i) {
		if (tmp % i) continue;
		while (tmp % i == 0) tmp /= i;
		fac.push_back(i);
	}
	if (tmp ^ 1) fac.push_back(tmp);
	int tot = fac.size();
	for (int i = 1; i <= n; ++ i) {
		LL x = 1;
		for (LL p : fac)
			while (a[i] % p == 0) x *= p, a[i] /= p;
		mp[a[i] = x].push_back(i);
	}
	for (auto pr : mp) {
		std::sort(pr.second.begin(), pr.second.end(), cmp);
		if (pr.second.size() > fac.size()) pr.second.resize(fac.size());
		for (int id : pr.second) {
			dv[0] = 1;
			LL cur = a[id];
			for (int i = 0; i < tot; ++ i) {
				dv[1 << i] = 1;
				while (cur % fac[i] == 0) cur /= fac[i], dv[1 << i] *= fac[i];
			}
			for (int s = 1; s < (1 << tot); ++ s) {
				if ((dv[s] = dv[s & (s - 1)] * dv[s & -s]) > lim) continue;
				cov[s].push_back(id);
			}
		}
	}
	for (int s = 1; s < (1 << tot); ++ s) {
		std::sort(cov[s].begin(), cov[s].end(), cmp);
		if (cov[s].size() > fac.size()) cov[s].resize(fac.size());
		// std::cout << s << " : ";
		// for (int id : cov[s]) std::cout << id << ' ';
		// std::cout << '\n';
		for (int id : cov[s]) trs[id].push_back(s);
	}
	for (int s = 0; s < (1 << tot); ++ s)
		for (int i = 0; i <= tot; ++ i) g[i][s] = f[i][s] = INF;
	f[0][0] = 0;
	for (int id = 1; id <= n; ++ id) {
		if (!trs[id].size()) continue;
		for (int s : trs[id]) {
			int t = ((1 << tot) - 1) ^ s, all = t;
			do {
				for (int i = 0; i < tot; ++ i)
					chkmin(g[i + 1][s | t], f[i][t] + c[id]);
				// std::cout << id << ' ' << s << ' ' << t << '\n';
				t = (t - 1) & all;
			} while (t != all);
		}
		for (int s : trs[id]) {
			int t = ((1 << tot) - 1) ^ s, all = t;
			do {
				for (int i = 1; i <= tot; ++ i)
					chkmin(f[i][s | t], g[i][s | t]), g[i][s | t] = INF;
				t = (t - 1) & all;
			} while (t != all);
		}
	}
	LL res = INF;
	for (int i = 0; i <= tot; ++ i)
		if (f[i][(1 << tot) - 1] != INF) chkmin(res, f[i][(1 << tot) - 1] * i);
	std::cout << (res == INF ? -1 : res) << '\n';
	return 0;
}