【动态规划组合数学放球问题】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 <= 10⁴
1 <= maxValue <= 10⁴

动态规划+放球问题

分两步：
一，利用动态规划计算理想数组忽略重复元素（令此数组为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$2¹³] 共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

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

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

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

本文涉及知识点

本题同解

LeetCode2338. 统计理想数组的数目