制定 dp 问题 [Codeforces 414 B]

Question

所有这些都是 problem statement 来自 codeforces 的旧比赛

A sequence of l integers b 1, b 2, ..., b l (1 ≤ b 1 ≤ b 2 ≤ ... ≤ b l ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all i (1 ≤ i ≤ l - 1).

Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).

我已经将我的 dp[i][j] 公式化为长度为 i 的好序列的数量，它以 j^th 数字结尾，并且转换 table 如下伪代码

dp[k][n] = 
  for each factor of n as i do
    for j from 1 to k - 1
      dp[k][n] += dp[j][i]
    end
  end

但社论中给出的是

Lets define dp[i][j] as number of good sequences of length i that ends in j.

Let's denote divisors of j by x1, x2, ..., xl. Then dp[i][j] = sigma dp[i - 1][xr]

但据我了解，我们需要两个西格玛，一个用于除数，另一个用于长度。请帮我纠正一下我的理解。

我的代码 ->

MOD = 10 ** 9 + 7

N, K = map(int, input().split())

dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]

for k in range(1, K + 1):
    for n in range(1, N + 1):
        c = 1
        for i in range(1, n):
            if n % i != 0:
                continue
            for j in range(1, k):
                c += dp[j][i]
        dp[k][n] = c

c = 0
for i in range(1, N + 1):
    c = (c + dp[K][i]) % MOD
print(c)

Link 问题：https://codeforces.com/problemset/problem/414/B

Answer 1

因此，让我们将 dp[i][j] 定义为长度为恰好 i 且最后一个元素以值 j 结尾的好序列的数量。

现在，对于所有 x s.t，dp[i][j] = Sum(dp[i-1][x])。 x 是 i 的约数。请注意，x 可以等于 j 本身。

这是真的，因为如果我们已经找到了一些长度为 i-1 的序列以某个值 x 结尾，那么我们可以简单地将 j 添加到它的末尾并形成一个满足所有条件的新序列.

我想您的困惑在于长度。问题是，由于我们当前的长度是 i，所以只有当序列的长度是 i-1 时，我们才能将 j 添加到序列的末尾，我们不能迭代其他长度。

希望这是清楚的。

制定 dp 问题 [Codeforces 414 B]

Formulating dp problem [Codeforces 414 B]

algorithm

dynamic-programming