https://codeforces.com/contest/414/problem/B
输入 u n(1≤u,n≤2000)。
输出有多少个长为 n 的数组 a,满足:
1. 1≤a[1]≤a[2]≤…≤a[n]≤u。
2. a[i] 整除 a[i+1](或者说 a[i] 是 a[i+1] 的因子)。
答案模 1e9+7。
输入 3 2
输出 5
输入 6 4
输出 39
输入 2 1
输出 2
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, MOD = 1e9 + 7;
int dp[N][N];
int main ()
{
int n, m;
cin >> m >> n;
for(int i = 1; i <= m; i ++) dp[1][i] = 1;
for(int i = 1; i <= n - 1; i ++)
{
for(int j = 1; j <= m; j ++)
{
for(int k = j; k <= m; k += j){
dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % MOD;
}
}
}
int res = 0;
for(int j = 1; j <= m; j ++) res = (res + dp[n][j]) % MOD;
cout << res << endl;
return 0;
}
赞
棒棒的呀~