codeforce每日一题
题目链接
题目分数:1400
题目描述
输入 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。
样例
输入样例1
3 2
输出样例1
5
输入样例2
6 4
输出样例2
39
算法
(dp) $O(n\*m\*log(m))$
我们可以用$dp$,$f[i][j]$表示前$i$位最后一位数字是$j$的总的方案数,转移方程$f[i][j\*k]=(f[i][j*k] + f[i-1][j])%mod$.
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2000 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9+7;
int n, m;
LL f[N][N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>m>>n;
rep(i, 1, m) f[1][i] = 1;
rep(i, 2, n)
rep(j, 1, m)
rep(k, 1, m)
if(k * j <= m) f[i][k * j] = (f[i][k * j] + f[i - 1][j]) % mod;
else break;
LL res = 0;
rep(i, 1, m) res = (res + f[n][i]) % mod;
cout<<res<<endl;
return 0;
}
Java 代码
// https://www.acwing.com/blog/content/34755/
import java.util.*;
public class Main{
public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f, mod = 1000000007;
public static void solve()
{
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();int n = sc.nextInt();
long[] f = new long[m + 1];
f[1] = 1;
for(int i = 0; i < n; i ++)
for(int j = m; j > 0; j --)
for(int k = j * 2; k <= m; k += j)
f[k] = (f[k] + f[j]) % mod;
long res = 0;
for(int i = 1; i <= m; i ++) res = (res + f[i]) % mod;
System.out.println(res);
}
public static void main(String[] args)
{
solve();
}
}
Python 代码
# https://www.acwing.com/blog/content/34755/
mod = int(1e9 + 7)
def solve():
m, n = map(int, input().split())
f = [0] * (m + 1)
f[1] = 1
for i in range(n):
for j in range(m, 0, -1):
k = j * 2
while k <= m:
f[k] = (f[k] + f[j]) % mod
k += j
res = sum(f[1 : m + 1])
print(res % mod)
def main():
solve()
if __name__ == '__main__':
main()