本文共 1120 字，大约阅读时间需要 3 分钟。

序列

时间限制:1000MS

内存限制:128000KB

题目描述

一个长度为k的整数序列b1，b2，…，bk（1≤b1≤b2≤…≤bk≤N）称为“好序列”当且仅当后一个数是前一个数的倍数，即bi+1是bi的倍数对任意的i（1≤i≤k-1）成立。 给定N和k，请算出有多少个长度为k的“好序列”，答案对1000000007取模。

输入

输入共1行，包含2个用空格隔开的整数N和k。

输出

输出共1行，包含一个整数，表示长度为k的“好序列”的个数对1000000007取模后的结果。

输入样例

3 2

输出样例

5

说明

【输入输出样例说明】

“好序列”为：[1,1]，[1,2]，[1,3]，[2,2]，[3,3]。

【数据说明】

对于40%的数据，1≤N≤30，1≤k≤10。 对于100%的数据，1≤N≤2000，1≤k≤2000。

解题思路

DP

F[i][j]表示序列长度为i且序列最后一个数b[i] =j的“好序列”的个数

F[i][j]=∑F[i-1][x]其中x为j的约数 可以先预处理出1-n每个数的约数

∑：为求和

AC代码

#include
   
    #include
    
     #include
     
      using namespace std;long long n,k,s,k1,b[2005],a[2005][2005],f[2005][2005];int main(){   	scanf("%lld%lld",&n,&k1);	for(long long i=1;i<=n;i++)//预处理约数	 for(long long j=1;j<=sqrt(i);j++)	  if(i%j==0)	  {   		if(j*j==i)a[i][++b[i]]=j;//特判		else a[i][++b[i]]=j,a[i][++b[i]]=i/j;	  }	for(long long i=1;i<=n;i++)//初值	 f[1][i]=1;	for(long long i=2;i<=k1;i++)//dp	 for(long long j=1;j<=n;j++)	  for(long long k=1;k<=b[j];k++)	   f[i][j]=(f[i][j]+f[i-1][a[j][k]])%1000000007;//取模	for(long long i=1;i<=n;i++)//最后每个都要累加	 s=(s+f[k1][i])%1000000007;	printf("%lld",s);	return 0;}
     
    
   

下面附本次比赛的其它题目

谢谢