algorithm - 有多少种方法可以构造一个大小为 N 的数组，使得任意一对连续元素的乘积不大于 M？

Question

每个元素都是一个整数，并且值至少应为 1。

约束条件:2 ≤ N ≤ 1000 和 1 ≤ M ≤ 1000000000。

我们需要对 1000000007 求模

Answer 1

也许我们可以计算 dp[len][type][typeValue]，其中 type 只有两种状态:

type = 0:这意味着，序列中最后一个长度 len 等于或小于 sqrt(M) 的数字.我们将这个数字保存在 typeValue

中

type = 1:这意味着序列中的最后一个数字大于 sqrt(M) .我们在 typeValue 中保存数字 k = M / lastNumber (向下舍入)，不大于 sqrt(M) .

所以，这个 dp 有 O(N sqrt(M))状态，但我们如何计算此 dp 的每个“单元格”？

首先，考虑一些“细胞”dp[len][0][number]。该值可以计算如下:

dp[len][0][number] = sum[1 <= i <= sqrt(M)] (dp[len - 1][0][i]) + sum[number <= i <= sqrt(M)] (dp[len - 1][1][i])

一点解释:因为type = 0 => number <= sqrt(M) , 所以我们可以输入任何不大于 sqrt(M) 的数字接下来，只有少数更大。

对于 dp[len][1][number] 我们可以使用下一个等式: dp[len][1][k] = sum[1 <= i <= k] (dp[len - 1][0][i] * cntInGroup(k))其中 cntInGroup(k) - cnt 编号 x这样 M / x = k

我们可以简单地计算出cntInGroups(k)对于所有 1 <= k <= sqrt(M)使用二进制搜索或公式。

但另一个问题是算法需要O(sqrt(M))操作所以结果渐近是O(N M) .但我们可以改进这一点。

请注意，我们需要计算在上一步处理的段 上的某些值的总和。因此，我们可以预先计算前缀和，然后我们可以计算 O(1) 中 dp 的每个“单元格”。时间。

因此，通过这种优化，我们可以用渐近 O(N sqrt(M)) 解决这个问题