【codeforces 415D】Mashmokh and ACM(普通dp)

【codeforces 415D】Mashmokh and ACM

题意:美丽数列定义:对于数列中的每一个i都满足:arr[i+1]%arr[i]==0

输入n,k(1<=n,k<=2000),问满足【数列长度是k && 数列中每一个元素arr[i]在1~n之间 && 数列中元素可以重复】的数列有多少个?结果对10^9+7取余

解题思路:dp[i][j]表示长度是j,最后一位是i的种数

if(kk%i==0) dp[kk][j+1]+=dp[i][j]

 #include <bits/stdc++.h>
using namespace std;
const int mod=1e9+;
int dp[][];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
memset(dp, , sizeof(dp));
for(int i=; i<=n; i++) dp[i][] = ;
for(int i=; i<=n; i++){
for(int kk=i; kk<=n; kk+=i){
for(int j=; j<=k; j++){
dp[kk][j] = (dp[kk][j]+dp[i][j-])%mod;
}
}
}
int ans=;
for(int i=; i<=n; i++) ans = (ans+dp[i][k])%mod;
printf("%d\n", ans);
return ;
}
上一篇:【codeforces 707C】Pythagorean Triples


下一篇:【codeforces 707E】Garlands