1994.好子集的数目

链接：1994.好子集的数目
难度：Hard
标签：位运算、数组、数学、动态规划、状态压缩
简介：请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

题解 1 - cpp

• 编辑时间：2022-02-22
• 执行用时：220ms
• 内存消耗：179.2MB
• 编程语言：cpp
• 解法介绍：dfs 遍历，对于所有可重合因子进行遍历，可在每个方案中增加 1 的可能性，每个方案都可以选择任意一个 1 或者不选择，总可能性为 pow(2, cnt1)。

int mod = 1e9 + 7;
#define MAX 40
unordered_map<int, int> m = {
    {23, 0b00000000010000000000000000000000},
    {19, 0b00000000000001000000000000000000},
    {17, 0b00000000000000010000000000000000},
    {15, 0b00000000000000000000000000010100},
    {14, 0b00000000000000000000000001000010},
    {13, 0b00000000000000000001000000000000},
    {30, 0b00000000000000000000000000010110},
    {11, 0b00000000000000000000010000000000},
    {29, 0b00010000000000000000000000000000},
    {10, 0b00000000000000000000000000010010},
    {26, 0b00000000000000000001000000000010},
    {7, 0b00000000000000000000000001000000},
    {6, 0b00000000000000000000000000000110},
    {5, 0b00000000000000000000000000010000},
    {22, 0b00000000000000000000010000000010},
    {3, 0b00000000000000000000000000000100},
    {21, 0b00000000000000000000000001000100},
    {2, 0b00000000000000000000000000000010},
    {1, 0b00000000000000000000000000000001},
};
int mod = 1e9 + 7;
#define MAX 40
class Solution {
   public:
    int arr[MAX] = {0}, num1;
    int numberOfGoodSubsets(vector<int> &nums) {
        for (auto &num : nums) {
            if (m.count(num)) arr[num]++;
        }
        num1 = qpow(2, arr[1]);
        long long ans = 0;
        for (int num = 2; num < MAX; num++) {
            if (arr[num]) dfs(ans, num, m[num], arr[num]);
        }
        return ans % mod;
    }
    void dfs(long long &ans, int num, int bits, long long sum) {
        ans = (ans + sum * num1) % mod;
        for (int nnum = num + 1; nnum < MAX; nnum++) {
            if (arr[nnum] == 0 || m[nnum] & bits) continue;
            dfs(ans, nnum, bits | m[nnum], sum * arr[nnum] % mod);
        }
    }
    int qpow(int a, int b) {
        long long ans = 1, tmp = a;
        while (b) {
            if (b & 1) ans = (ans * tmp) % mod;
            tmp = (tmp * tmp) % mod;
            b >>= 1;
        }
        return ans;
    }
};