题解 | #牛牛与数组#

//
// Created by HuJJun on 2021/10/16.
//

#include<iostream>
#include<cstring>
using namespace std;
long long const MOD=1e9+7;

bool const test = false;  //设置为true 可以答应dp过程

long long dp[15][100005];   // dp[长度][结尾数字]
int N,K;
void output(){
    if(!test) return ;
    for(int i = 1 ; i <= N ; i++) {
        cout << i << ":";
        for (int j = 1; j <= K; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}
void init(){
    for(int i = 1 ; i <= N ; i++)
        for (int j = 1; j <= K; j++)
            dp[i][j]= (i==1 ? 1 : 0);
    output();
}
int main() {
    cin >> N >> K;

    init();
    long long sum = K;  //设置初始 当i=1,共有K种
    for (int i = 2; i <= N; i++) {  //长度
        long long nextSum = 0;
        for (int j = 1; j <= K; j++) {  // j结尾数字
            //正向求解,k大于10000超时
            //*
            //k为前一个数
            for(int k = 1 ; k < j ; k++)    //k<j 满足条件一
                for(int kt = k ; kt <= K ; kt+=j)   //那k加上j的倍数满足条件二
                    dp[i][j] += dp[i-1][kt];
            dp[i][j] += dp[i-1][j]; //当k==j时 满足条件一
            dp[i][j] %= MOD;
            /*/
            //逆向求解
            dp[i][j] = sum % MOD;   //设置为上一条长度满足条件个数
            for (int k = j * 2; k <= K; k += j)   //j的倍数,不满足条件
                dp[i][j] = (dp[i][j] - dp[i - 1][k] + MOD) % MOD;   // 扣除上一长度的倍数个数
            nextSum = (nextSum + dp[i][j]) % MOD; //统计当前长度满足条件个数和
            //*/
        }
        sum = nextSum; //保存，下一长度需要使用
    }

    output();

    sum = 0;

    for (int i = 1; i <= K; i++)    //答案求和
        sum = (sum + dp[N][i]) % MOD;


    cout << sum << endl;

    return 0;
}