Description

Solution

Observing that the numbers are in range [1,30] and two same numbers except 1 are interchangeble, we can reduce the size of the problem by making it a problem of combinations of unique numbers between [1,30]. For example, if we have [2, 2, 2, 2, 4, 3, 3, 15], then we can reduce it to [2, 3, 4, 15], and think about the combination problem later.

For numbers in range [1, 30], there are 3 types:
a. 1
b. the numbers that have one prime number occuring multiple times as its factor(abandon them obviously)
c. the numbers that have distince prime factors

For the number 1, it can be appended to any subset to double the number of combinations, and we will make this step that last one.

Only keeping type c numbers, the numbers we should consider can be reduced from [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30] to [2,3,4,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30](totally 19 numbers at maximum).

The problem now we are trying to solve is which number should occur in a subset. If we try all, there are 2^19 = 524288 possibilities using bitmask, which is acceptable.

To reduce the overhead inside the bitmask, we can further compress those distinct prime factors information as bits in integers for each of these numbers we consider.

Now we should try to make sure that for each of the two numbers in a given bitmask state, their logical and result is 0. To achieve that, we can store the accumulative logical OR result and check if its logical AND result with an incoming prime factor bitmask is 0.

class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        const int M = 1e9 + 7;
        unordered_set<int> possibleNums {2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30};

        vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

        int nOnes = 0;
        map<int, int> counter;
        for(int x: nums) {
            if(x == 1) {
                nOnes++;
                continue;
            }
            if(!possibleNums.count(x)) continue;
            counter[x]++;
        }

        vector<int> bitmask;
        vector<int> numbers;

        for(auto [num, cnt]: counter) {
            int t = 0;
            for(int i = 0; i < primes.size() && primes[i] <= num; ++i) {
                if(num % primes[i] == 0) t += (1 << i);
            }
            bitmask.push_back(t);
            numbers.push_back(num);
        }

        int n = bitmask.size();
        
        long long ret = 0;
        for(int state = 1; state < (1 << n); ++state) {
            int total = 0;
            bool isValid = true;
            for(int i = 0; i < n; ++i) {
                if((state>>i)&1) {
                    if(!(total & bitmask[i])) {
                        total |= bitmask[i];
                    } else {
                        isValid = false;
                        break;
                    }
                }
            }

            if(isValid) {
                long long product = 1;
                for(int i = 0; i < n; ++i) {
                    if((state>>i)&1) product = (product * counter[numbers[i]]) % M;
                }
                ret = (ret + product) % M;
            }
        }

        for(int i = 0; i < nOnes; ++i) {
            ret = (ret << 1) % M;
        }

        return ret;

    }
};