luogu CF414B Mashmokh and ACM |动态规划

如果一个数列中,后一个数都能被前面一个数整除,那么就叫这个数列为好数列。输入n,k,求数列中最大元素为n,数列长度为k的好数列的种数(对1000000007取模)


#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int mod=1e9+7;
inline int read(){
	int x=0; char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while('0'<=c&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); }
	return x;
}
int f[2002][2002],ans;
signed main(){
	int n=read(),k=read();
	for(int i=0;i<=n;i++)f[1][i]=1;	
	for(int i=2;i<=k;i++)
	for(int j=1;j<=n;j++)
	for(int _=1;_*j<=n;_++)
	f[i][j]=(f[i][j]+f[i-1][j*_])%mod;
	for(int i=1;i<=n;i++)ans=(ans+f[k][i])%mod;
	printf("%lld
",ans);
}
原文地址:https://www.cnblogs.com/naruto-mzx/p/12678316.html