lc-1994-the-number-of-good-subsets.org

LC 1994. 好子集的数目

https://leetcode-cn.com/problems/the-number-of-good-subsets/

这题的nums的数量非常多，但是范围却非常小，所以从范围入手是个好主意，对于重复出现的数字其实性质是一样的。

从1-30范围内的素数以及符合基本条件的数字也就是下面这么多

• primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
• good_numbers = [2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30] # size = 18

我们可以把每个 good_numbers 里面的数字挂在对应的素数下面，那么这个组合的情况其实不多。

实现中还有个问题要考虑的是，比如15如果挂在了3下面就不要挂在5下面，不然在选择的时候会出现

• 在3下面选择15，在5下面不选择
• 在3下面不选择，在5下面选择15

出现重复计算的情况，所以我们选择某一个prime进行挂载就好了。

还可能出现个问题是，比如对于7和14，如果14挂在了2下面，而7挂在了7下面，他们之间还是可能有公约数的情况，所以在搜索的时候， 我们可能还是需要判断，选择某个数是否和之前的选择数是互质的。因为范围比较小，所以这个gcd可以预先打表计算出来。

最后我们要把1排除在外，对于每个1有选择或者是不选择两种情况，所以结果需要乘以 `1<<(cnt[1])`

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        good_numbers = [2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30]
        coprimes = set()

        def gcd(x, y):
            while y != 0:
                x, y = y, x % y
            return x

        for x in range(1, 31):
            for y in range(1, 31):
                if gcd(x, y) == 1:
                    coprimes.add((x, y))

        cnt = [0] * 31
        for x in nums:
            cnt[x] += 1

        counters = []
        for p in primes:
            tmp = []
            for x in good_numbers:
                if x % p == 0 and cnt[x] != 0:
                    tmp.append((x, cnt[x]))
                    cnt[x] = 0  # not select anymore
            counters.append(tmp)

        def dfs(k, select):
            if k == len(primes):
                return 1

            res = dfs(k + 1, select)
            for x, c in counters[k]:
                ok = True
                # for p in select:
                #     if (x, p) not in coprimes:
                #         ok = False
                #         break

                if ok:
                    select.append(x)
                    res += c * dfs(k + 1, select)
                    select.pop()

            return res

        # print(counters)

        # including empty set.
        ans = dfs(0, []) - 1
        ans *= (1 << cnt[1])

        MOD = 10 ** 9 + 7
        return ans % MOD