Codeforces 1198F - GCD Groups 2

丢人了,随机跑的和状压一样快。这说明我随机写的很好?

乍一看没有思路,看了下 $\mbox{tutorial}$ 发现最多能够被分解成 $9$ 个质数,那么现在就有一个随机算法了:

随机选两个数分属两个集合,分别分解他们的质因数,现在需要消去这些质因数:将剩下的数随机加,使得达到删除某些质因数的效果,最后检查是否为 $1$ ,即删掉所有的质因数。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

#define MAXN 100005

using namespace std;

int n;
pair<int, int> s[MAXN];
int belong[MAXN];
clock_t base = clock();

struct division {
int p[MAXN], v[MAXN], total, temp;

division() {
memset(p, 0, sizeof(p));
memset(v, 0, sizeof(v));
total = temp = 0;
}

void init() {
for (int i = 1; i <= total; ++i)
v[i] = p[i] = 0;
temp = total = 0;
}

void decompose(int x) {
init();
int limit = sqrt(x);
for (int i = 2; i <= limit; ++i)
if (x % i == 0) {
p[++total] = i;
while (x % i == 0)
x /= i;
}
if (x != 1)
p[++total] = x;
}
}A, B;

int read() {
char c = getchar();
int x = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}

int crand(int mod) {
return 1ll * rand() * rand() % mod + 1;
}

bool kill(division& t, int x) {
bool islegal = false;
for (int i = 1; i <= t.total; ++i)
if (!t.v[i] && x % t.p[i] != 0) {
t.v[i] = true;
islegal = true;
++t.temp;
}
return islegal;
}

int main() {
srand((int)time(0));
n = read();
for (int i = 1; i <= n; ++i) {
s[i].first = read();
s[i].second = i;
}
while ((clock() - base) * 2.520 <= CLOCKS_PER_SEC) {
random_shuffle(s + 1, s + n + 1);
int a = crand(n), b = crand(n);
A.decompose(s[a].first);
B.decompose(s[b].first);
belong[s[a].second] = 1;
belong[s[b].second] = 2;
if (a == b)
continue;
for (int i = 1; i <= n; ++i) {
if (i == a || i == b)
continue;
if (kill(A, s[i].first))
belong[s[i].second] = 1;
else {
kill(B, s[i].first);
belong[s[i].second] = 2;
}
}
if (A.temp == A.total && B.temp == B.total) {
puts("YES");
for (int i = 1; i <= n; ++i)
printf("%d ", belong[i]);
return 0;
}
}
puts("NO");
}

状压就是先选出两个数使得他们分属两个集合,分解质因数,可以计算出一个数加到某一个集合后会使哪些质因数消失,状压表示集合, $\mbox{DP}$ 求可行解 ,这样是 $O(n2^{2k})$ 的。

对于一个质因数,我们只需要任选 $2k$ 个没有这个质因数的其他数字,这样保证一定有情况能使该质因数被消去,关于任选的正确性:因为选了 $2k$ 个,合法情况下一定有至少一个会剩下,所以该质因数一定可以被消掉。

我讨厌这个算法,又难写空间开销还大还一样快!!!

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>

#define MAXN 100005
#define MAXB 18

using namespace std;

int n, m;
int s[MAXN], t[MAXN];
int belong[MAXN], used[MAXN];
clock_t base = clock();
int pa[MAXN], pb[MAXN], A, B;
bool ischosen[MAXN];
int f[2][1 << MAXB], from[1 << MAXB], decision[1 << MAXB], part[1 << MAXB], amount[3];

int read() {
char c = getchar();
int x = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}

int crand(int mod) {
return 1ll * rand() * rand() % mod + 1;
}

void divide(int* p, int& total, int x) {
int limit = sqrt(x);
total = 0;
for (int i = 2; i <= limit; ++i)
if (x % i == 0) {
p[++total] = i;
while (x % i == 0)
x /= i;
}
if (x != 1)
p[++total] = x;
}

void enlist(int* p, int total) {
for (int i = 1; i <= total; ++i)
for (int j = 1, k = 0; j <= n && k <= A + B; ++j)
if (s[j] % p[i]) {
ischosen[j] = true;
++k;
}
}

int keep(int* p, int total, int x) {
int s = 0;
for (int i = 1; i <= total; ++i)
if (x % p[i])
s |= 1 << (i - 1);
return s;
}

int main() {
srand((int)time(0));
n = read();
for (int i = 1; i <= n; ++i)
s[i] = read();
while ((clock() - base) * 2.520 <= CLOCKS_PER_SEC) {
memset(ischosen, 0, sizeof(ischosen));
memset(f, 0, sizeof(f));
memset(amount, 0, sizeof(amount));
int a = crand(n), b = crand(n);
if (a == b)
continue;
divide(pa, A, s[a]);
divide(pb, B, s[b]);
belong[a] = 1;
belong[b] = 2;
enlist(pa, A);
enlist(pb, B);
m = 0;
for (int i = 1; i <= n; ++i)
if (ischosen[i]) {
t[++m] = s[i];
used[m] = i;
}
int limit = (1 << (A + B)) - 1;
f[0][0] = 1;
for (int i = 1; i <= m; ++i) {
int cur = i & 1;
memcpy(f[cur], f[cur ^ 1], sizeof(f[cur]));
if (used[i] == a || used[i] == b)
continue;
int s1 = keep(pa, A, t[i]), s2 = keep(pb, B, t[i]) << A;
for (int s = limit - 1; s >= 0; --s) {
if (f[cur ^ 1][s]) {
if ((s & s1) != s1 && !f[cur][s | s1]) {
f[cur][s | s1] = 1;
decision[s | s1] = used[i];
from[s | s1] = s;
part[s | s1] = 1;
}
if ((s & s2) != s2 && !f[cur][s | s2]) {
f[cur][s | s2] = 1;
decision[s | s2] = used[i];
from[s | s2] = s;
part[s | s2] = 2;
}
}
}
}
if (f[m & 1][limit]) {
int s = limit;
while (s) {
belong[decision[s]] = part[s];
++amount[part[s]];
s = from[s];
}
puts("YES");
for (int i = 1; i <= n; ++i)
printf("%d ", belong[i] ? belong[i] : 1);
return 0;
}
}
puts("NO");
}