本文共 1057 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算给定最大元素n和长度k的“好数列”的总个数。好数列的定义是每个后续元素都能被前一个元素整除。

方法思路

我们可以使用动态规划来解决这个问题。我们定义一个二维数组dp，其中dp[i][j]表示以j结尾且长度为i的好数列的个数。状态转移方程的关键在于找到j的因数，并将dp[i-1][j]的值加到dp[i][t]中，其中t是j的倍数。

具体步骤如下：

解决代码

#include 
   
    using namespace std;const int mod = 1e9 + 7;int dp[2005][2005]; // 初始化为0int main() {    int n, k;    cin >> n >> k;        // 初始化长度为1的情况    for (int j = 1; j <= n; ++j) {        dp[1][j] = 1;    }        for (int i = 2; i <= k; ++i) {        for (int j = 1; j <= n; ++j) {            for (int t = j; t <= n; t += j) {                dp[i][t] = (dp[i][t] + dp[i-1][j]) % mod;            }        }    }        int sum = 0;    for (int j = 1; j <= n; ++j) {        sum = (sum + dp[k][j]) % mod;    }        cout << sum << endl;    return 0;}
   

代码解释

这个方法通过动态规划高效地计算了所有可能的好数列，确保了计算的正确性和效率。