【动态规划 组合数学 放球问题】2338. 统计理想数组的数目

2024-05-31 14:12
文章标签 动态 规划 问题 统计 数组 组合 数学 数目 理想 放球 2338

本文主要是介绍【动态规划 组合数学 放球问题】2338. 统计理想数组的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

动态规划汇总
组合数学汇总
【组合数学 隔板法 容斥原理】放球问题

本题同解

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

LeetCode2338. 统计理想数组的数目

给你两个整数 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

动态规划+放球问题

分两步：
一，利用动态规划计算理想数组忽略重复元素（令此数组为arr）的的数目。比如：[1,1,2]和[1,2,2]相同。
二，第一步的方案对应多少种理想数组。如：[1,2] 对应[1,1,2]和[1,2,2]。显然n和非重复元素的数量确定时，对应的方案数是确定的。就是放球问题：球同，盒子不同，不能为空。

动态规划的状态表示

dp[len][max] 长度为len，最后的值为max的不重复数组arr数量。

动态规划的转移方程

通过前置条件更新后置条件。
next 是iMax的倍数，且大于iMax。
枚举已知条件，iMax len
dp[len+1][next] += dp[len][iMax]

动态规划的初始值

全部为1。

动态规划的填表顺序

iMax（1：maxLen)和len(2:14) arr[i+1] > arr[i] 且是倍数关系。至少是2倍。极端情况是:[1,2,4$\cdots$213] 共14个元素。

代码

核心代码

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;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();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;;
};template<int MOD = 1000000007>
C1097Int<MOD> Pow(const C1097Int<MOD>& bi1, long long ii2) {return	bi1.pow(ii2);
}template<class T >
class CFactorial
{
public:CFactorial(int n):m_res(n+1){m_res[0] = 1;for (int i = 1; i <= n; i++) {m_res[i] = m_res[i - 1] * i;}}	T Com(int iSel, int iCanSel)const {return m_res[iCanSel] / m_res[iSel]/ m_res[iCanSel - iSel];}T Com(const vector<int>& cnt)const {T biRet = 1;int iCanSel = std::accumulate(cnt.begin(), cnt.end(), 0);for (int j = 0; j < cnt.size(); j++) {biRet *= Com(cnt[j], iCanSel);iCanSel -= cnt[j];}return biRet;}vector<T> m_res;
};template<class T>
class CBallBox
{
public:CBallBox(CFactorial<T>& fac,int n,int m):m_fac(fac),m_iN(n),m_iM(m){}T NotNotNot() {//球不同盒子不同不能为空return g(m_iM);}T NotIsNot() {//球不同盒子同不能为空return NotNotNot()/ m_fac.m_res[m_iM];}T IsNotIs() {//球同盒子不同能为空return m_fac.Com(m_iM - 1, m_iN + m_iM - 1);}T IsNotNot(){//球同盒子不同不能为空if (m_iN < m_iM) { return 0; }return m_fac.Com(m_iM - 1, m_iN  - 1);}const int m_iM, m_iN;
protected:	T g(int m)const {T biRet;for (int i = 0; i <= m; i++) {	auto cur = m_fac.Com(i, m)  * Pow(T(m - i), m_iN);if (1 & i) {biRet -= cur;}else {biRet += cur;}}return biRet;}CFactorial<T>& m_fac;
};class Solution {
public:int idealArrays(int n, int maxValue) {static auto vCnt = Init();C1097Int<> biRet = 0;static CFactorial<C1097Int<>> fac(10'000 + 20);for (int len = 1; len <= 14; len++) {CBallBox<C1097Int<>> ballBox(fac,n,len);auto cur = ballBox.IsNotNot()*vCnt[len][maxValue];biRet += cur;}return biRet.ToInt();}vector < vector<C1097Int<>>> Init(){const int iMaxMax = 10'000;vector < vector<C1097Int<>>> dp(14+1, vector < C1097Int<>>(iMaxMax + 1));for (int iMax = 1; iMax <= iMaxMax; iMax++) {dp[1][iMax] = 1;}for (int len = 1; len < 14; len++) {for (int iMax = 1; iMax <= iMaxMax; iMax++) {for (auto next = iMax * 2; next <= iMaxMax; next += iMax) {				dp[len + 1][next] += dp[len][iMax];}}		}vector < vector<C1097Int<>>> dp2 = dp;for (int iMax = 2; iMax <= iMaxMax; iMax++) {for (int len = 1; len <= 14; len++) {dp2[len][iMax] += dp2[len][iMax - 1];}}return dp2;}
};

测试用例

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);}}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

这篇关于【动态规划 组合数学 放球问题】2338. 统计理想数组的数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1018152。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu4869（逆元+求组合数）

hdu4869（逆元+求组合数）

//输入n，m，n表示翻牌的次数，m表示牌的数目，求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
uva 10014 Simple calculations（数学推导）

uva 10014 Simple calculations（数学推导）

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导，第二次没有继续下去。 代码： #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2