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

本文涉及知识点

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

本题同解

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

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:1∑j​dp[i−1][j−x]
必须通过前缀和优化，否则时间复杂度?(qnn)，超时。

返回值

∑ x : 1 q ( ∑ ( d p 1 [ x ] ) ⋆ ( ∑ ( d p 2 [ x ] ) ) \sum _{x:1}^{q} (\sum(dp1[x])\star (\sum(dp2[x])) x:1∑q​(∑(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();
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111

测试用例


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);
	}
		
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

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 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++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览61211 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/135968018"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！