DEV Community
·
2338. 计算理想数组的数量
💡
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定两个整数n和maxValue，理想数组的长度为n，元素范围在1到maxValue之间，且每个元素必须是前一个元素的倍数。通过组合数学和动态规划计算不同的理想数组数量，结果需对10^9 + 7取模。
🎯
关键要点
-
给定两个整数n和maxValue，描述理想数组的长度和元素范围。
-
理想数组的每个元素必须是前一个元素的倍数。
-
返回不同的理想数组数量，结果需对10^9 + 7取模。
-
示例1：n=2，maxValue=5，输出为10。
-
示例2：n=5，maxValue=3，输出为11。
-
理想数组是非递减的。
-
解决方案涉及组合数学和动态规划。
-
每个元素的质因数必须包含前一个元素的质因数。
-
使用组合计数计算有效序列的数量。
-
预计算阶乘和逆阶乘以高效计算组合数。
-
对每个值v，计算质因数的组合数乘积并求和。
-
该方法高效处理约束，避免暴力枚举所有可能的序列。
❓
延伸问答
什么是理想数组？
理想数组是长度为n，元素范围在1到maxValue之间，且每个元素必须是前一个元素的倍数的数组。
如何计算理想数组的数量？
通过组合数学和动态规划，计算每个值的质因数组合数乘积并求和，最后对10^9 + 7取模。
能给出理想数组的示例吗？
例如，n=2，maxValue=5时，理想数组有10种可能：[1,1], [1,2], [2,2]等。
理想数组的元素有什么限制？
理想数组的每个元素必须是前一个元素的倍数，并且是非递减的。
为什么要对结果取模？
因为理想数组的数量可能非常大，所以需要对10^9 + 7取模以避免溢出。
如何预计算阶乘和逆阶乘？
使用模运算预计算阶乘和逆阶乘，以便高效计算组合数。
➡️
