[Hackerrank] Array Partition (并查集, 数学)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.hackerrank.com/contests/hourrank-29/challenges/array-partition

给n个数，让你将这n个数拆分成两个集合，使得两个集合分别乘积互质，求拆分方案数。

第一次打Hackerrank，一个小时三道题还是很刺激的。这道题比赛的时候没调出来，只拿了部分分，有点遗憾啊~）ps：衣服还是很难拿的，top10 才有，这场出现了tourist等众神牛，这种场拿衣服还是不想了。

根据题目的要求，显然拥有相同因数的数字必须呆在同一个集合（1除外，这是个trick，后面会说），考虑用一个方法，将所有拥有至少一个公共因数的数字划为同一个集合，然后再对所有不连通的集合进行计数，会发现：当有$n$个集合的时候，我们的划分方案数为$2^{n}-2$。

很显然可以用并查集维护每一个数的因数的连通情况，因此我们在枚举每一个数的因数的同时，将因数和这个数并到一起就可以了。这里需要特别注意的是，每一个1都可以分到一个单独的集合里，因此计数的时候需要单独考虑~

整体复杂度为$O(n\sqrt{n})$

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
typedef long long LL;
const int maxn = 1000010;
const LL mod = 1e9+7;

int pre[maxn];
set<int> vis;

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void unite(int x, int y) {
  x = find(x); y = find(y);
  if(x != y) {
    pre[x] = y;
  }
}

int solve(vector<int> a) {
  int cnt = 0;
  int nn = 1 << a.size();
  vis.clear();
  for(int i = 0; i < maxn; i++) pre[i] = i;
  for(int i = 0; i < a.size(); i++) {
    if(a[i] == 1) cnt++;
    vis.insert(a[i]);
    int tmp = a[i];
    int aa = (int)sqrt(a[i]) + 1;
    for(int j = 2; j <= aa; j++) {
      if(tmp % j == 0) {
        unite(a[i], j);
        vis.insert(j);
        while(tmp % j == 0) tmp /= j;
      }
    }
    if(tmp != 1) unite(a[i], tmp);
  }
  map<int, int> block;
  for(int i = 0; i < maxn; i++) {
    if(vis.find(i) != vis.end()) {
      block[find(i)]++;
    }
  }
  if(block.size() < 2) {
    return 0;
  }
  LL ret = 1;
  for(int i = 0; i < block.size(); i++) {
    ret *= 2;
    ret %= mod;
  }
  for(int i = 0; i < cnt - 1; i++) {
    ret *= 2;
    ret %= mod;
  }
  ret -= 2; ret += mod; ret %= mod;
  return ret;
}