好子集的数目

/*
 * This solution uses Java Streams to process the input array and compute the number of good subsets.
 * We use a HashMap to store the frequency of each number and filter those that can form a valid product of distinct primes.
 * The implementation also handles numbers with repeated prime factors that cannot form good subsets.
 */
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class GoodSubsetsStream {
    private static final int MOD = 1000000007;
    private static final int[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

    public int numberOfGoodSubsets(int[] nums) {
        Map<Integer, Long> freq = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

        long[] dp = new long[1 << PRIMES.length];
        dp[0] = 1;  // empty set

        freq.entrySet().stream()
            .filter(entry -> entry.getKey() > 1)
            .forEach(entry -> {
                int num = entry.getKey();
                long count = entry.getValue();
                int subsetMask = getPrimeMask(num);
                if (subsetMask != -1) {
                    IntStream.iterate((1 << PRIMES.length) - 1, i -> i >= 0, i -> i - 1)
                        .filter(state -> (state & subsetMask) == 0)
                        .forEach(state -> dp[state | subsetMask] = (dp[state | subsetMask] + dp[state] * count) % MOD);
                }
            });

        long result = IntStream.range(1, dp.length).mapToLong(i -> dp[i]).sum() % MOD;
        long countOfOnes = freq.getOrDefault(1, 0L);
        if (countOfOnes > 0) {
            result = (result * powMod(2, countOfOnes)) % MOD;
        }

        return (int) result;
    }

    private int getPrimeMask(int num) {
        int mask = 0;
        for (int i = 0; i < PRIMES.length; i++) {
            int prime = PRIMES[i];
            if (num % (prime * prime) == 0) return -1;
            if (num % prime == 0) mask |= (1 << i);
        }
        return mask;
    }

    private long powMod(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return result;
    }
}