ZOJ Monthly, March 2018 - H 动态规划

题目描述

对于一个长度为k的数列，若每一个元素都能整除后面一个元素，则称之为快乐数列。现在给出n和m，找出n以内的所有长度为m的快乐数列，输出数量。

Sample Input

1 3
2

Sample output

5

问题分析

设dp[i][j]为长度为i，结尾数字为j的数列。那么容易得到状态转移公式$dp[i][j] = \sum dp[i-1][k]$,其中k是能整除j的所有正整数。那么最后答案即为$\sum dp[m]i.先预处理一下小于2000的所有数的因子

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int modd = 1e9 + 7;
const int maxn = 2000 + 10;
int dp[maxn][maxn];  //长度为n，结尾数字为m
vector<int> num[maxn];

void init()
{
  for(int i=1;i<=2000;i++)
    for(int j=i;j>=1;j--)
      if((i%j) == 0)  num[i].push_back(j);  //预处理因子
  for(int i=1;i<=2000;i++)  dp[1][i] = 1;
  for(int i=2;i<=2000;i++)
    for(int j=1;j<=2000;j++)
      for(int k=0;k<num[j].size();k++)
        dp[i][j] = (dp[i][j] + dp[i-1][num[j][k]]) % modd;
}

int main()
{
  init();
  int kase,n,m;
  LL ans;
  cin >> kase;
  while(kase--)
  {
    ans = 0;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
      ans += dp[m][i];
    }
    cout << ans % modd << endl;
  }
}