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

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

int main(){

    //dp[i][j]表示的含义是前i个整数，以j结尾的时候，有多少喜欢的数列
    //转义方程dp[i][j] = sum(dp[i-1][1,2,3,...,k])  -  sum(dp[i-1][x], x > j and x % j == 0)
    // 当新增加固定一个数的时候，这个新串的种类数，就是不增加这一位时所有喜欢数列种类之和, 再减去前一位中不满足(A <= B)或(A mod B != 0)这条性质的串
    const int num = 1000000007;
    int n, k;
    cin>>n>>k;
    vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
    dp[0][1] = 1; 
    for (int i  = 1; i <=n; i++){

        //sum(dp[i][1,2,3,...,k])
        int sum = 0;
        for (int j = 1; j <=k; j++){
            sum += dp[i-1][j];
            sum %= num;
        }

        for (int x = 1; x <=k; x++){
            //sum(dp[i-1][y], y > x and y % x == 0 )
            int one_sum = 0;
            for (int y = x+x; y <=k; y += x){
                one_sum += dp[i-1][y];
                one_sum %= num;
            }
            dp[i][x] = (sum - one_sum + num) % num; // i 个x这种情况·
            //cout<<i<<" "<<x<<" "<< sum <<" "<< one_sum<<" " << dp[i][x]<<endl;
        }
    }
    int result = 0;
    for (int i = 1; i <= k; i++){
        result += dp[n][i];
        result %= num;
    }
    cout<<result<<endl;
}