题解 | #小易喜欢的数列#

小易喜欢的数列

https://www.nowcoder.com/practice/49375dd6a42d4230b0dc4ea5a2597a9b

解题思路

这是一个动态规划问题，需要计算满足条件的数列个数
定义 $dp[i][j]$ 表示长度为 $i+1$ 且最后一个数字为 $j$ 的合法数列个数
对于每个位置，我们需要：
- 统计前一个位置所有数字的方案总和
- 减去不满足条件的方案数（即对于当前数 $j$ ，减去所有是 $j$ 倍数位置的方案数）
最终答案是最后一行所有位置的方案数之和
由于答案可能很大，需要对 $1000000007$ 取模

代码

cpp
java
python

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    const int mod = 1000000007;
    
    // dp[i][j]表示长度为i+1且最后一个数字为j的合法数列个数
    vector<vector<int>> dp(n, vector<int>(k+5, 0));
    
    // 初始化长度为1的情况
    for (int i = 1; i <= k; ++i)
        dp[0][i] = 1;
        
    // 动态规划过程
    for (int i = 1; i < n; ++i) {
        // 计算前一行的和
        int sum = 0;
        for (int j = 1; j <= k; ++j) {
            sum = (sum + dp[i-1][j]) % mod;
        }
        
        // 对每个数字计算当前位置的方案数
        for (int j = 1; j <= k; ++j) {
            dp[i][j] = sum;
            // 减去不满足条件的情况
            for (int mul = j*2; mul <= k; mul += j) {
                dp[i][j] = (dp[i][j] - dp[i-1][mul] + mod) % mod;
            }
        }
    }
    
    // 计算最终答案
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
        ans = (ans + dp[n-1][i]) % mod;
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        final int mod = 1000000007;
        
        int[][] dp = new int[n][k+5];
        
        // 初始化
        for (int i = 1; i <= k; ++i)
            dp[0][i] = 1;
            
        // 动态规划
        for (int i = 1; i < n; ++i) {
            int sum = 0;
            for (int j = 1; j <= k; ++j) {
                sum = (sum + dp[i-1][j]) % mod;
            }
            
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = sum;
                for (int mul = j*2; mul <= k; mul += j) {
                    dp[i][j] = ((dp[i][j] - dp[i-1][mul]) % mod + mod) % mod;
                }
            }
        }
        
        // 计算结果
        int ans = 0;
        for (int i = 1; i <= k; ++i) {
            ans = (ans + dp[n-1][i]) % mod;
        }
        
        System.out.println(ans);
    }
}

def solve(n, k):
    mod = 1000000007
    dp = [[0] * (k+5) for _ in range(n)]
    
    # 初始化
    for i in range(1, k+1):
        dp[0][i] = 1
        
    # 动态规划
    for i in range(1, n):
        # 计算前一行的和
        sum_prev = sum(dp[i-1][j] for j in range(1, k+1)) % mod
        
        # 计算当前行
        for j in range(1, k+1):
            dp[i][j] = sum_prev
            # 减去不满足条件的情况
            mul = j * 2
            while mul <= k:
                dp[i][j] = (dp[i][j] - dp[i-1][mul]) % mod
                mul += j
    
    # 计算最终答案
    ans = sum(dp[n-1][i] for i in range(1, k+1)) % mod
    return ans

n, k = map(int, input().split())
print(solve(n, k))