无平方子集计数

You are given a positive integer 0-indexed array nums.

A subset of the array nums is square-free if the product of its elements is a square-free integer.

A square-free integer is an integer that is divisible by no square number other than 1.

Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo 109 + 7.

A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

 

Example 1:

Input: nums = [3,4,4,5]
Output: 3
Explanation: There are 3 square-free subsets in this example:
- The subset consisting of the 0th element [3]. The product of its elements is 3, which is a square-free integer.
- The subset consisting of the 3rd element [5]. The product of its elements is 5, which is a square-free integer.
- The subset consisting of 0th and 3rd elements [3,5]. The product of its elements is 15, which is a square-free integer.
It can be proven that there are no more than 3 square-free subsets in the given array.

Example 2:

Input: nums = [1]
Output: 1
Explanation: There is 1 square-free subset in this example:
- The subset consisting of the 0th element [1]. The product of its elements is 1, which is a square-free integer.
It can be proven that there is no more than 1 square-free subset in the given array.

 

Constraints:

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

/*
题目思路：
1. 使用Stream API处理输入的数组。
2. 过滤掉包含平方因子的数字。
3. 使用动态规划来计算无平方子集的数量。
4. 初始化dp数组表示使用前i个数字可以组成的无平方子集的数量。
5. 遍历每个数字，如果它可以加入当前的无平方子集，则更新状态数组。
6. 最终结果是dp数组所有状态的和，取模10^9+7。
*/
import java.util.*;
import java.util.stream.*;

public class NoSquareSubsetsStream {
    public int noSquareSubsets(int[] nums) {
        int MOD = 1000000007;
        int n = nums.length;
        nums = Arrays.stream(nums).filter(num -> !containsSquare(num)).toArray();
        n = nums.length;
        int[] dp = new int[1 << n];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = (1 << n) - 1; j >= 0; j--) {
                if ((j & (1 << i)) == 0) continue;
                dp[j] = (dp[j] + dp[j ^ (1 << i)]) % MOD;
            }
        }
        int result = 0;
        for (int i = 1; i < (1 << n); i++) {
            result = (result + dp[i]) % MOD;
        }
        return result;
    }

    private boolean containsSquare(int num) {
        return IntStream.rangeClosed(2, (int)Math.sqrt(num)).anyMatch(i -> num % (i * i) == 0);
    }
}

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

O(n * 2^10)

O(2^10)