题目链接:
题目大意:
定义一个序列,前一项能够整除后一项,给定这个序列中数的取值范围和序列的长度,问有多少种构造方法。
题目分析:
- 我们定义状态dp[i][j]为前i项已经确定且第i项为j的方案数。
- 转移方程 dp[i][j]=∑k|jdp[i−1][k]
- 复杂度O(n⋅k)
AC代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define MAX 2007
using namespace std;
typedef long long LL;
int n,k;
const LL mod=1e9+7;
LL dp[MAX][MAX];
int main ( )
{
while ( ~scanf ( "%d%d" , &n , &k ) )
{
memset ( dp , 0 , sizeof ( dp ) );
for ( int i = 1 ; i <= n ; i++ )
dp[1][i] = 1;
for ( int i = 2 ; i <= k ; i++ )
for ( int j = 1 ; j <= n ; j++ )
for ( int k = 1 ; k*k<=j ; k++ )
{
if ( j%k ) continue;
dp[i][j] += dp[i-1][k];
dp[i][j] %= mod;
int x = j/k;
if ( x == k ) continue;
dp[i][j] += dp[i-1][x];
dp[i][j] %= mod;
}
int ans = 0;
for ( int i = 1 ; i <= n ; i++ )
{
ans += dp[k][i];
ans %= mod;
}
printf ( "%d\n" , ans );
}
}