1994. 好子集的数目

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
typedef long long LL;
class Solution {
 public:
  int numberOfGoodSubsets(vector<int>& nums) {
    const int mod = 1e9 + 7;
    int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int cnt[35] = {0};
    int n = nums.size();
    for (auto& x : nums) cnt[x]++;
    int s = 1 << 10;
    LL f[1030] = {0};
    f[0] = 1;
    for (int i = 2; i <= 30; i++) {
      if (cnt[i] == 0) continue;
      int cur = 0, x = i;
      bool ok = true;
      for (int j = 0; j < 10; j++) {
        int t = p[j], c = 0;
        while (x % t == 0) {
          cur |= (1 << j);
          x /= t;
          c++;
        }
        if (c > 1) {
          ok = false;
          break;
        }
      }
      if (!ok) continue;
      for (int prev = s - 1; prev >= 0; prev--) {
        if ((prev & cur) != 0) continue;
        f[prev | cur] = (f[prev | cur] + f[prev] * cnt[i]) % mod;
      }
    }
    LL ans = 0;
    for (int i = 1; i < s; i++) ans = (ans + f[i]) % mod;
    for (int i = 0; i < cnt[1]; i++) ans = ans * 2 % mod;
    return (int)ans;
  }
};