本文涉及知识点
动态规划 状态机dp 状态压缩 分组
LeetCode1994. 好子集的数目
给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。
比方说，如果 nums = [1, 2, 3, 4] ：
[2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 23 ，6 = 23 和 3 = 3 。
[1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 22 和 4 = 22 。
请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。
nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。
示例 1：
输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
示例 2：
输入：nums = [4,2,3,15]
输出：5
解释：好子集为： - [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 30
原理
m = max(nums)，最大为30。
一，子集就是子序列。空子序列显然不符合要求。
二，1无法表示成质数相乘，所以乘积为1(全部为1的子序列)的忽略。
三，一二结合，先排除空序列，再处理1。
四，除1外，其它数最多只能选一次。1最后处理，排除空序列后，1可以任意选择。有x个1，就有2x种选法。
五，如果一个数包括两个质因数的平方，则忽略，如：4,8,16。
变量解释
m最大为30，故只需要考虑10个质因数。mask &(1 << i) 表示第i个质因数是否使用。
vPrime 记录前30个质数。
vMask[x] 记录x包括那些质数。
cnt[x] 记录x的个数。
vx记录[2,m]中不包括相同质因子的数。
超时的状态表示
dp[i][j] 表示处理了num前i个元素，j表示质因数的使用情况。空间复杂度：O(n 210) ≈ \approx≈ 108
除一外，每个数字只会选择一次，故只需要考虑x是否被选择，如果被选择，需要数乘以cnt[x]，表示可以选择任意一个。
动态规划处理[2,m]
动态规划的状态表示
dp[i][j]表示已经处理了[2,i)，正在处理i ，质数使用情况为j的数量。
空间复杂度:O(210m)。
动态规划的转移方程
pre表示dp[i-1],dp表示dp[i]。
i不被选择dp = pre。
枚举前置状态。
如果!(iPre&vMask[x]) 也就两者没有相同的质因数
dp[iPre| vMask[x]] += pre[iPre]*cnt[x];
转移方程时间复杂度：O(1)，总时间复杂度：O(210m)
动态规划的初始状态
pre[0]=1，其它全部为0。
动态规划的返回值
auto biRet = std::accumulate(vPre.begin(), vPre.end(), C1097Int(-1));//排除空子集 biRet *= C1097Int<>(2).pow(cnt[1]);
动态规划的填表顺序
i从2到m。
代码
vector<int> CreatePrime(int iMax) { vector<int> vNo(iMax + 1); vector<int> vPrime; for (int i = 2; i <= iMax; i++) { if (!vNo[i]) { vPrime.emplace_back(i); } for (const auto& n : vPrime) { if( n * i > iMax ) { break; } vNo[n * i] = true; } } return vPrime; } template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator==(const C1097Int& o)const { return m_iData == o.m_iData; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class Solution { public: int numberOfGoodSubsets(vector<int>& nums) { auto vPrime = CreatePrime(30); const int iMaskCount = 1 << vPrime.size(); int vMask[31] = { 0 }; for (int i = 1; i <= 30; i++) { for (int j = 0; j < vPrime.size(); j++) { if (0 != i % vPrime[j]) { continue; } vMask[i] |= (1 << j); } } int cnt[31] = { 0 }; for (const auto& n : nums) { cnt[n]++; } vector<int> vx; for (int x = 2; x <= 30; x++) { bool bNeed = true; for (int j = 0; (j < vPrime.size()) && (vPrime[j] * vPrime[j] <= x);j++) { if (0 == x % (vPrime[j] * vPrime[j])) { bNeed = false; } } if (bNeed) { vx.emplace_back(x); } } vector<C1097Int<>> vPre(iMaskCount); vPre[0] = 1; for (auto x : vx) { vector<C1097Int<>> dp = vPre; for (int iPre = 0; iPre < iMaskCount; iPre++) { if (iPre & vMask[x]) { continue; }//质因数重复 dp[iPre | vMask[x]] += vPre[iPre] * cnt[x]; } vPre.swap(dp); auto biRet = std::accumulate(vPre.begin(), vPre.end(), C1097Int(-1));//排除空子集 std::cout << "x:" << x << " " << biRet.ToInt() << std::endl; } auto biRet = std::accumulate(vPre.begin(), vPre.end(), C1097Int(-1));//排除空子集 biRet *= C1097Int<>(2).pow(cnt[1]); return biRet.ToInt(); } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; { Solution sln; nums = { 1,1 }; auto res = sln.numberOfGoodSubsets(nums); Assert(0, res); } { Solution sln; nums = { 1,2,3,4 }; auto res = sln.numberOfGoodSubsets(nums); Assert(6, res); } { Solution sln; nums = { 4,2,3,15 }; auto res = sln.numberOfGoodSubsets(nums); Assert(5, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
