无平方子集计数

标签: 位运算 数组 数学 动态规划 状态压缩

难度: Medium

给你一个正整数数组 nums 。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 109 + 7 取余的结果。

nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。

示例 1：

输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。

示例 2：

输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 30

Submission

运行时间: 43 ms

内存: 16.1 MB

PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

def convert_mask(num):
    if num == 1:
        return -1
    mask = 0
    for i, p in enumerate(PRIMES):
        if num % p == 0:
            if num % (p*p) == 0:
                return -1
            mask |= 1<<i
    return mask


class Solution:
    def squareFreeSubsets(self, nums: List[int]) -> int:
        MOD = 10**9+7
        cnts = Counter(nums)
        MASK = (1<<10) - 1
        dp = [1] + [0] * MASK
        for num, cnt in cnts.items():
            m = convert_mask(num)
            if m == -1:
                continue
            fill = sub = m ^ MASK
            while True:
                dp[sub|m] = (dp[sub|m] + dp[sub]*cnt)%MOD 
                sub = (sub-1)&fill
                if sub == fill:
                    break 
        
        return (sum(dp) * pow(2, cnts[1], MOD) - 1) % MOD
            


# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/count-the-number-of-square-free-subsets/solutions/2121032/liang-chong-xie-fa-01bei-bao-zi-ji-zhuan-3ooi/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

此题解采用了动态规划结合位掩码的方式来解决问题。首先，它定义了一个列表 PRIMES 包含所有小于 30 的素数。使用 convert_mask 函数将每个数字转换为一个位掩码，表示其质因数的存在情况。若数字含有任何质数的平方因子，则该数字不能用于形成无平方子集，此时返回 -1。对于数组中的每个数字，统计其出现次数，然后利用动态规划的方式更新每种可能的位掩码组合。动态规划的状态 dp[mask] 表示以 mask 为质因数掩码的子集的数量。最后，计算总的子集数量，特别注意要乘以2的幂次方，以包含数字1的所有可能组合，最后减去空集。

时间复杂度: O(n * 2^10)

空间复杂度: O(2^10)

PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)

def convert_mask(num):
    # 转换数字为位掩码，排除包含平方因子的数
    if num == 1:
        return -1
    mask = 0
    for i, p in enumerate(PRIMES):
        if num % p == 0:
            if num % (p*p) == 0:
                return -1
            mask |= 1<<i
    return mask

class Solution:
    def squareFreeSubsets(self, nums: List[int]) -> int:
        MOD = 10**9+7
        cnts = Counter(nums)
        MASK = (1<<10) - 1
        dp = [1] + [0] * MASK
        for num, cnt in cnts.items():
            m = convert_mask(num)
            if m == -1:
                continue
            fill = sub = m ^ MASK
            while True:
                dp[sub|m] = (dp[sub|m] + dp[sub]*cnt)%MOD 
                sub = (sub-1)&fill
                if sub == fill:
                    break 
        return (sum(dp) * pow(2, cnts[1], MOD) - 1) % MOD

Explore

题解中的`convert_mask`函数的作用是将每个数转换为一个位掩码，该掩码表示数的质因数。对于每个数，函数遍历已定义的素数列表PRIMES，检查该数是否能被素数整除。如果该数能被素数的平方整除，则函数会返回-1，表示此数包含平方因子，不能用于形成无平方子集。如果仅能被素数整除一次，则将相应的素数索引位置的位设置为1。这样，通过返回的掩码，我们可以知道该数的质因数组成，而含有平方因子的数被直接排除掉，不参与后续的动态规划计算。

在动态规划的更新过程中，使用位掩码来管理状态，确保每个子集的质因数组合是唯一的。`dp`数组的索引是位掩码，表示当前子集包含的质因数。对于每个数字，计算其位掩码`m`，然后遍历与`m`不重叠的所有掩码组合`sub`（通过`sub = (sub-1)&fill`实现），并更新`dp[sub|m]`。这里的更新是基于`dp[sub]`的现有值，且每次更新都是独立的，因为`sub|m`的结果对于每个不同的`sub`是唯一的，从而避免了重复计算相同的因子子集。

在题解中，`cnts[1]`表示数字1在输入数组中出现的次数。由于1没有任何质因数，它可以与数组中的任何其他子集自由组合而不会增加新的质因数约束。因此，对于每个1，都有选取或不选取两种可能，即如果有`cnts[1]`个1，就有`2^cnts[1]`种可能的组合方式。最终结果需要乘以`pow(2, cnts[1], MOD)`，是为了包括所有这些组合在内。这样做是因为动态规划的计算过程中未将1纳入考虑，所以最后需要额外计算1的组合数，以得到完整的子集数量。