【动态规划】【前缀和】【数学】2338. 统计理想数组的数目

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode:2338. 统计理想数组的数目

给你两个整数 n 和 maxValue ,用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ,如果满足以下条件,则认为该数组是一个 理想数组 :
每个 arr[i] 都是从 1 到 maxValue 范围内的一个值,其中 0 <= i < n 。
每个 arr[i] 都可以被 arr[i - 1] 整除,其中 0 < i < n 。
返回长度为 n 的 不同 理想数组的数目。由于答案可能很大,返回对 109 + 7 取余的结果。
示例 1:
输入:n = 2, maxValue = 5
输出:10
解释:存在以下理想数组:

  • 以 1 开头的数组(5 个):[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
  • 以 2 开头的数组(2 个):[2,2]、[2,4]
  • 以 3 开头的数组(1 个):[3,3]
  • 以 4 开头的数组(1 个):[4,4]
  • 以 5 开头的数组(1 个):[5,5]
    共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。
    示例 2:
    输入:n = 5, maxValue = 3
    输出:11
    解释:存在以下理想数组:
  • 以 1 开头的数组(9 个):
    • 不含其他不同值(1 个):[1,1,1,1,1]
    • 含一个不同值 2(4 个):[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
    • 含一个不同值 3(4 个):[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
  • 以 2 开头的数组(1 个):[2,2,2,2,2]
  • 以 3 开头的数组(1 个):[3,3,3,3,3]
    共计 9 + 1 + 1 = 11 个不同理想数组。
    提示:
    2 <= n <= 104
    1 <= maxValue <= 104

动态规划

令 m =maxValue

直接动态规划超时

dp[i][j]记录 长度为i,以j结尾的子序列数量。状态数:O(mn),每种状态转移的时间复杂度:O( m \sqrt m m )。约1010,超时。

预处理

vNext[i]包括x,表示x被i整除,且大于i,且<=maxValue。此部分的时间复杂度空间复杂度都是O(m m \sqrt {m} m )。

动态规划除重后的数量

除重后,最大长度14 {20,21 , ⋯ \cdots ,2^13},令p= 14。
dp1[i][j] 记录除重后,长度为i,以j结尾的数量。空间复杂😮(qm) 转移所有dp[i]的时间复杂度:O(m m \sqrt {m} m ),总时间复杂度:O(nm m \sqrt m m )
dp[0]忽略,dp[1][0]为0,其它为1。
通过前者状态更新后置状态。 F o r x : v N e x t [ j ] \Large For_{x:vNext[j]} Forx:vNext[j]dp[i][x] += dp[i][j]

动态规划

dp2[i][j] 从i个不同的数中选择j个数的选择数量,每个数至少选择一个。枚举后置状态。
d p [ i ] [ j ] = ∑ x : 1 j d p [ i − 1 ] [ j − x ] dp[i][j] =\sum _{x:1}^{j} dp[i-1][j-x] dp[i][j]=x:1jdp[i1][jx]
必须通过前缀和优化,否则时间复杂度😮(qnn),超时。

返回值

∑ x : 1 q ( ∑ ( d p 1 [ x ] ) ⋆ ( ∑ ( d p 2 [ x ] ) ) \sum _{x:1}^{q} (\sum(dp1[x])\star (\sum(dp2[x])) x:1q((dp1[x])((dp2[x]))

代码

核心代码

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;}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 idealArrays(int n, int maxValue) {vector<vector<int>> vNext(maxValue + 1);for (int i = 1; i <= maxValue; i++){for (int j = i * 2; j <= maxValue; j += i){vNext[i].emplace_back(j);}}const int q = 14;vector<vector<C1097Int<> >> dp1(q + 1, vector<C1097Int<> >(maxValue + 1));dp1[1].assign(maxValue + 1,1);dp1[1][0] = 0;for (int i = 1; i < q; i++){for(int j = 0 ; j <= maxValue; j++ ){ for (const auto& next : vNext[j]){dp1[i + 1][next] += dp1[i][j];}}}vector<vector<C1097Int<> >> dp2(q + 1, vector<C1097Int<> >(n + 1));dp2[0][0] = 1;for (int i = 1; i <= q; i++){C1097Int biSum = dp2[i - 1][0];for (int j = 1; j <= n; j++){				dp2[i][j] = biSum;biSum += dp2[i - 1][j];}}C1097Int biRet;for (int i = 1; i <= q; i++){biRet += std::accumulate(dp1[i].begin(),dp1[i].end(),C1097Int())* dp2[i].back();}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()
{	int n,  maxValue;{Solution sln;n = 2, maxValue = 5;auto res = sln.idealArrays(n, maxValue);Assert(res,10);}{Solution sln;n = 5, maxValue = 3;auto res = sln.idealArrays(n, maxValue);Assert(res, 11);}{Solution sln;n = 1000, maxValue = 1000;auto res = sln.idealArrays(n, maxValue);Assert(res, 91997497);}{Solution sln;n = 10000, maxValue = 10000;auto res = sln.idealArrays(n, maxValue);Assert(res, 22940607);}}

2023年2月

class Solution {
public:
int idealArrays(int n, int maxValue) {
m_n = n;
m_vPosNeedSel.assign(n + 1, vector(20, 0));
m_vPosNeedSel[1].assign(20,1);
for (int i = 2; i <= n; i++)
{
for (int j = 0; j < 20; j++)
{
//全部选择第一个位置
m_vPosNeedSel[i][j] += 1;
//第一个位置选择k个
for (int k = 0; k < j; k++)
{
m_vPosNeedSel[i][j] += m_vPosNeedSel[i - 1][j-k];
}
}
}
for (int i = 1; i <= maxValue; i++ )
{
Do(i);
}
return m_iRet.ToInt();
}
void Do(int i)
{
C1097Int aNum = 1 ;
for (int j = 2; j*j <= i; j++)
{
int iNumj = 0;
while (0 == i% j)
{
iNumj++;
i /= j;
}
aNum *= m_vPosNeedSel[m_n][iNumj];
}
if (i > 1)
{
aNum *= m_vPosNeedSel[m_n][1];
}
m_iRet += aNum;
}
vector<vector> m_vPosNeedSel;
int m_n;
C1097Int m_iRet = 0;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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://xiahunao.cn/news/2774606.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

React环境配置

1.安装Node.js Node.js官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…

JAVA结课作品——超市管理系统

项目描述&#xff1a;一个简单的超市管理系统&#xff0c;能够实现用户登入和注册功能&#xff0c;共分为前台和后台两个主要界面&#xff0c;普通用户界面操作权限收到限制&#xff0c;只能对商品和销售记录进行简单查询操作&#xff0c;后台中可以进行商品的删除、修改、查询…

如何使用Docker本地部署一个开源网址导航页并分享好友公网使用

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;…

PHP入门指南:进阶篇

PHP入门指南&#xff1a;进阶篇 PHP入门指南&#xff1a;进阶篇1. 面向对象编程&#xff08;OOP&#xff09;1.1 类和对象的基本概念1.2 构造函数和析构函数1.3 属性和方法的访问控制1.4 继承与多态 2. 错误和异常处理2.1 错误处理机制2.2 异常处理机制2.3 自定义异常类 3. PHP…

【GAMES101】Lecture 19 相机

目录 相机 视场 Field of View (FOV) 曝光&#xff08;Exposure&#xff09; 感光度&#xff08;ISO&#xff09; 光圈 快门 相机 成像可以通过我们之前学过的光栅化成像和光线追踪成像来渲染合成&#xff0c;也可以用相机拍摄成像 今天就来学习一下相机是如何成像的…

NeRF从入门到放弃1:原理介绍

基本概念 原始的论文中所介绍的NeRF&#xff08;NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis&#xff0c;用神经辐射场表示场景进行视角合成&#xff09;&#xff0c;是神经辐射场以及体积渲染技术的结合&#xff0c;即用神经辐射场隐式地表示场…

代码随想录算法训练营第29天|491.递增子序列 * * 46.全排列 * 47.全排列 II

文章目录 491.递增子序列思路&#xff1a;代码 思路&#xff1a;优化代码&#xff1a; 46.全排列思路代码一&#xff1a;使用used数组代码二&#xff1a;使用path判断元素 47.全排列 II思路一&#xff1a;层节点和路径都是用used数组做记录思路二&#xff1a;层通过排序后是否重…

【第二届 Runway短视频创作大赛】——截至日期2024年03月01日

短视频创作大赛 关于AI Fil&#xff4d; Festival竞赛概况参加资格报名期间报名方法 提交要求奖品附录 关于AI Fil&#xff4d; Festival 2022年成立的AIFF是一个融合了最新AI技术于电影制作中的艺术和艺术家节日&#xff0c;让我们得以一窥新创意时代的风采。从众多参赛作品中…

C语言笔试题之实现C库函数 strstr()(设置标志位)

实例要求&#xff1a; 1、请你实现C库函数strstr()&#xff08;stdio.h & string.h&#xff09;&#xff0c;请在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;&#xff1b;2、函数声明&#xff1a;int strStr(char* h…

MATLAB知识点:易错点:判断浮点数是否相等

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第3章 3.4.3 关系运算 下面我们再来看一个易错点&…

flask+pyinstaller实现mock接口,并打包到exe运行使用postman验证

flask代码 from flask import Flask, request, jsonifyapp Flask(__name__)app.route("/login", methods[POST]) def login():username request.json.get("username").strip() # 用户名password request.json.get("password").strip() # 密…

林浩然的趣味解读:赫伯特·亚历山大·西蒙的跨界智慧与伟大成就

林浩然的趣味解读&#xff1a;赫伯特亚历山大西蒙的跨界智慧与伟大成就 Lin Haoran’s Amusing Interpretation: Herbert Alexander Simon’s Interdisciplinary Wisdom and Great Achievements 林浩然&#xff0c;这位机智幽默且对知识充满好奇的探索者&#xff0c;最近在一次…

代码随想录算法训练营第二十四天 |回溯算法基础知识,77.组合(已补充)

回溯算法理论基础&#xff08;已观看&#xff09; 带你学透回溯算法&#xff08;理论篇&#xff09;| 回溯法精讲&#xff01;_哔哩哔哩_bilibili #题目分类 什么是回溯法 溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 在二叉树系列中&#xff0c;我们已经不…

2022年通信工程师初级 实务 真题

文章目录 三、第3章 接入网&#xff0c;接入网的功能结构&#xff0c;无线频段及技术四、第4章 互联网&#xff0c;网络操作系统的功能&#xff0c;IP地址五、第6章 移动通信系统&#xff0c;FDD、TDD 三、第3章 接入网&#xff0c;接入网的功能结构&#xff0c;无线频段及技术…

numa网卡绑定

#概念 参考&#xff1a;https://www.jianshu.com/p/0f3b39a125eb(opens new window) chip&#xff1a;芯片&#xff0c;一个cpu芯片上可以包含多个cpu core&#xff0c;比如四核&#xff0c;表示一个chip里4个core。 socket&#xff1a;芯片插槽&#xff0c;颗&#xff0c;跟…

【Spring Boot】第二篇 自动装配原来就这么简单

导航 一. 什么是自动装配?二. 如何实现自动装配?1. 配置清单在哪里?2. 自动装配实现核心点1: 从META‐INF/spring.factories路径读取配置类清单核心点2: 过滤第一次过滤: 根据EnableAutoConfiguration注解中exclude和excludeName属性第二次过滤: 通过AutoConfigurationImpor…

Java实现网上药店系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 药品类型模块2.3 药品档案模块2.4 药品订单模块2.5 药品收藏模块2.6 药品资讯模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 角色表3.2.2 药品表3.2.3 药品订单表3.2.4 药品收藏表3.2.5 药品留言表…

【集合系列】LinkedHashMap 集合

LinkedHashMap集合 1. 概述2. 方法3. 遍历方式4. 代码示例5. 注意事项 其他集合类 祖父类 Map 父类 HashMap 集合类的遍历方式 具体信息请查看 API 帮助文档 1. 概述 LinkedHashMap 是 Java 中的一种特殊类型的 HashMap&#xff0c;它继承自 HashMap 类&#xff0c;并实现了…

免费:阿里云学生服务器领取申请(2024新版教程)

2024年阿里云学生服务器免费领取&#xff0c;先完成学生认证即可免费领取一台云服务器ECS&#xff0c;配置为2核2G、1M带宽、40G系统盘&#xff0c;在云服务器ECS实例过期之前&#xff0c;完成实验与认证任务&#xff0c;还可以免费续费6个月&#xff0c;阿里云百科aliyunbaike…

2023爱分析·大模型厂商全景报告|爱分析报告

01 研究范围定义 研究范围 大模型是指通过在海量数据上依托强大算力资源进行训练后能完成大量不同下游任务的模型。2023年以来&#xff0c;ChatGPT引爆全球大模型市场。国内众多大模型先后公测&#xff0c;众多互联网领军者投身大模型事业&#xff0c;使得大模型市场进入“百团…