【状态机dp 状态压缩 分组】1994. 好子集的数目

embedded/2024/10/20 15:45:47/

本文涉及知识点

动态规划汇总
动态规划 状态机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++**实现。


http://www.ppmy.cn/embedded/24328.html

相关文章

unity项目《样板间展示》开发：菜单界面

unity项目《样板间展示》开发：菜单界面

unity项目《样板间展示》开发&#xff1a;菜单界面 前言UI菜单创建逻辑实现结语 前言 这是这个项目demo教程的最后一节&#xff0c;这节是菜单界面部分的创建 UI菜单创建 创建一个新的场景&#xff0c;在Scene文件中右键选择Create->Scene&#xff0c;创建新的场景 在场景…
阅读更多...
案例-部门管理-删除

案例-部门管理-删除

黑马程序员JavaWeb开发教程 文章目录 一、查看页面原型二、查看接口文档三、开发1、Controller2、Service&#xff08;1&#xff09;service接口层&#xff08;3&#xff09;service实现层 3、Mapper4、Postman 一、查看页面原型 二、查看接口文档 三、开发 1、Controller 因…
阅读更多...
Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之九 简单进行嘴巴检测并添加特效的功能实现

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之九 简单进行嘴巴检测并添加特效的功能实现

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之九 简单进行嘴巴检测并添加特效的功能实现 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之九 简单进行嘴巴检测并添加特效的功能实现 一、简单介绍 二、简单…
阅读更多...
有趣的大模型之我见 | Llama AI Model

有趣的大模型之我见 | Llama AI Model

Llama 开源吗&#xff1f; 我在写《有趣的大模型之我见 | Mistral 7B 和 Mixtral 8x7B》时曾犹豫&#xff0c;在开源这个事儿上&#xff0c;到底哪个大模型算鼻祖&#xff1f;2023 年 7 月 18 日&#xff0c;Meta 推出了最受欢迎的大型语言模型&#xff08;LLM&#xff09;的第…
阅读更多...
JVM调优

JVM调优

行性能监控和故障处理指令 操作系统工具 top&#xff1a;显示系统整体资源使用情况vmstat&#xff1a;监控内存和CPUiostat&#xff1a;监控IO使用netstat&#xff1a;监控网络使用JDK性能监控工具 jps&#xff1a;虚拟机进程查看jstat&#xff1a;虚拟机运行时信息查看jinfo&…
阅读更多...
Facebook的声音：听见社交媒体的心跳

Facebook的声音：听见社交媒体的心跳

社交媒体如今已经成为人们日常生活中不可或缺的一部分&#xff0c;而Facebook作为其中的佼佼者&#xff0c;承载着数以亿计的用户的交流、分享和连接。在这个信息爆炸的时代&#xff0c;Facebook的声音就像是社交媒体的心跳&#xff0c;传递着无数个体的情感、思想和生活。本文…
阅读更多...
【算法每日一练】动态规划，图论（换根dp）会议 ，医院设置

【算法每日一练】动态规划，图论（换根dp）会议 ，医院设置

目录 题目&#xff1a; 会议 思路&#xff1a; 题目&#xff1a;医院设置 思路&#xff1a; 题目&#xff1a; 会议 思路&#xff1a; 首先&#xff0c;阅读题目可以看出来&#xff0c;这道题目实际上就是求树的重心。 树的重心&#xff1a; 定义&#xff1a;找到一个点&a…
阅读更多...
【unocss】自用

【unocss】自用

unocss中文官网1 不知道简写的可以在这里查 第一步 npm install -D unocss第二步 // vite.config.ts import UnoCSS from unocss/vite import { defineConfig } from viteexport default defineConfig({plugins: [UnoCSS()] })// main.ts import virtual:uno.css第三步 在…
阅读更多...
最新文章

Copyright @ 2022~2023