自动搬运

查看原文

来自洛谷，原作者为

	Cripple_Abyss **

搬运于2025-08-24 21:35:00，当前版本为作者最后更新于2020-07-06 22:53:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

本题其实是一道基本的DP题，十分适合一些新手

DP三步法：

1. 设计状态：

   用 $f_{i\ j}$来表示符合条件的长度为 $i$ ，最后一个数为 $j$ 的序列个数

2. 推状态转移方程：

   f[i][j*k]=(f[i][j*k]+f[i-1][j])%mod

3. 设定初值：

   f[1][i]=1 

Code：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[2005][2005],ans;
int main() {
	cin>>n>>m;
	for (int i=1; i<=n; i++)
		f[1][i]=1;
	for (int i=2; i<=m; i++)
		for (int j=1; j<=n; j++)
			for (int k=1; k<=n/j; k++) 
				f[i][j*k]=(f[i][j*k]+f[i-1][j])%mod;
	for (int i=1; i<=n; i++) 
		ans=(ans+f[m][i])%mod;
	cout<<ans;
	return 0;
}

都看到这里了，点个赞呗QwQ