↓Skip to main content
  1. Posts/

LeetCode-2572 无平方子集计数

·1 min·
Table of Contents

LeetCode-2572 无平方子集计数 #

Solution 1 #

用 $s$ 记录因子状态, 状压 dp.

代码如下:

class Solution:
    def squareFreeSubsets(self, nums: List[int]) -> int:
        MOD = 1_000_000_007
        ps = [2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 27, 29]
        p2idx = {x: i for i, x in enumerate(ps)}

        def mask(k):
            s = 0
            for p in ps:
                if k % (p ** 2) == 0:
                    return -1
                if k % p == 0:  
                    s |= 1 << p2idx[p]
            return s

        nums = [mask(x) for x in nums if mask(x) != -1]
        n = len(nums)
        
        if n == 0:
            return 0

        dp = [[0 for _ in range((1 << (12)))] for _ in range(n)]
        dp[0][0] += 1
        dp[0][nums[0]] += 1
        for i in range(1, n):
            for j in range(0, (1<<12)):
                if j & nums[i] == 0:
                    dp[i][j | nums[i]] = (dp[i][j | nums[i]] + dp[i - 1][j]) % MOD
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD

        ans = 0
        for j in range(0, (1<<12)):
            ans = (ans + dp[n - 1][j]) % MOD
        return (ans + MOD - 1) % MOD