Leetcode 2572. Count the Number of Square-Free Subsets

[Woodyiiiiiii]

这道题重点在于如何计算满足条件的子集。其实观察数据大小就可以发现，可以枚举所有质数，然后使用bitmask状态压缩来计算子集。

难点：

1. 找到集合的乘法结果不会被一个数的平方整除
2. 如何计算集合的数目

第一点，其实就是质因数的定义，当我们计算一个数是否是质数的时候，就是靠从2开始枚举平方能否被该数整除，所以换句话说，题目条件是求集合的乘法结果是不是多个质因数的乘积。

第二点，接上上一点，这么多集合如何利用好有限的时间进行判断呢？我们可以发现数据的大小是有限的，进而可以枚举出所有的质因数，而且，多个质因数之间可以表示为多个不同的状态，每次加入一个数都是对状态的叠加。也就是bitmask的思路。

class Solution {
    final int[] factors = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

    public int squareFreeSubsets(int[] nums) {
        List<Integer> statusList = new ArrayList<>();
        for (int num : nums) {
            if (num == 1) {
                statusList.add(0);
                continue;
            }
            int status = getStatus(num);
            if (status != 0) statusList.add(status);
        }
        final int MOD = 1_000_000_007;
        Map<Integer, Integer> status2cntMap = new HashMap<>();
        for (int status : statusList) {
            Map<Integer, Integer> newStatus2cntMap = new HashMap<>();
            newStatus2cntMap.put(status, 1);
            for (Map.Entry<Integer, Integer> entry : status2cntMap.entrySet()) {
                int newStatus = entry.getKey() | status;
                if (newStatus != (entry.getKey() ^ status)) continue;
                newStatus2cntMap.put(newStatus, (newStatus2cntMap.getOrDefault(newStatus, 0) + entry.getValue()) % MOD);
            }
            // merge newStatus2cntMap to status2cntMap
            for (Map.Entry<Integer, Integer> entry : newStatus2cntMap.entrySet()) {
                status2cntMap.put(entry.getKey(), (status2cntMap.getOrDefault(entry.getKey(), 0) + entry.getValue()) % MOD);
            }
        }
        int ans = 0;
        for (int cnt : status2cntMap.values()) {
            ans = (ans + cnt) % MOD;
        }
        return ans;
    }

    private int getStatus(int num) {
        int status = 0;
        for (int i = 0; i < factors.length; i++) {
            int cnt = 0;
            int factor = factors[i];
            while (num % factor == 0) {
                status |= 1 << i;
                num /= factor;
                cnt++;
            }
            if (cnt > 1) return 0;
        }
        return status;
    }
}

类似题目：

• 2572. Count the Number of Square-Free Subsets
• 1994. The Number of Good Subsets
• 1986. Minimum Number of Work Sessions to Finish the Tasks