计数类dp

72 阅读 0 评论 48 点赞

我是靠谱客的博主不安大山，最近开发中收集的这篇文章主要介绍计数类dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

link

The robot overlord has a bit of a dilemma on his hands. The army has constructed a huge factory stocked with worker robots in order to make the next generation army. There are nn types of robots that the army is trying to build, each type having a unique ID which is an integer between 11 and nn (inclusive of 11 and nn).

Now, to meet the army's goal of world domination, they must construct kk robots every day (the type of each robot doesn't matter, just need kk total every day). However, his current batch of workers tends to be a little temperamental. They have threatened to go on strike unless their demands for the new robots were met. The overlord would usually just incinerate the obstinate robots and use the scrap parts to create a new workforce but due to the time crunch, the overlord decides to humor the workers.

The worker's demand is simple enough: they want each of the kk robots made that day to follow the rule that if the iith robot made is of type aa (1≤a≤n1≤a≤n) then the i+1i+1th robot made must be of type bb where a∣ba∣b. This must hold for all ii where 1≤i≤k−11≤i≤k−1 which means that if the sequence of robots made is r1,r2,…,rnr1,r2,…,rn then ri∣ri+1ri∣ri+1 for all ii (1≤i≤n−11≤i≤n−1).

Given nn and kk, help the overlord find out the number of distinct robot sequences that satisfy the above demand that can be made. Since this number can be quite large, the overlord will suffice with the number modulo 10000000071000000007 (109+7)(109+7).

Input

The only line of input will contain two space-separated integers nn and kk where 1≤n,k≤20001≤n,k≤2000.

Output

Output a single integer representing the number of distinct robot sequences that satisfy the workers' demand modulo 10000000071000000007 (109+7)(109+7).

Examples

input

4 2

output

input

6 5

output

Note

In the first sample, the sequences are [1,1],[2,2],[3,3],[4,4],[1,2],[1,3],[1,4],[2,4][1,1],[2,2],[3,3],[4,4],[1,2],[1,3],[1,4],[2,4].

题目大意：规定一个序列中含有k个数，且这些数处于1-n，并且满足后序列中前一个数字必须是后一个数的约数，如若n=8,k=3,则1,2,4 2,4,8 1,4,8都是合法的。问有几种满足要求的序列。

一眼dp,以二维dp[i,j]表示此时序列为i个数并且最后一个数是j的集合。如何转移？：dp[i,j]可以从dp[i,j的所有约数]转移过来，递推完后，答案便是dp[k,1]+dp[k,2]+.....dp[k,n].

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<malloc.h>
#include<numeric>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
int main()
{
long long dp[2010][2010] = { 0 };
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)dp[1][i] = 1;//初始化dp数组，所有仅含一个数的dp[][]值都是1
for (int i = 2; i <= k; i++)//从dp[2][]开始递推到dp[k][]
for (int j = 1; j <= n; j++)//dp[i][j],对于每个确定的i,j可以取1-n;
for (int m = 1; m <= j / m; m++)//找j的约数
if (j % m == 0)
{
if (j / m != m)//约数不==，即若25的因数5,5总不能加两个dp[i][5]吧！
dp[i][j] = (dp[i][j] + dp[i - 1][m] + dp[i - 1][j / m]) % 1000000007;
else
dp[i][j] = (dp[i][j] + dp[i - 1][m]) % 1000000007;//约数相等加其中一个便可
}
int res = 0;
for (int i = 1; i <= n; i++)res = (res + dp[k][i]) % 1000000007;
cout << res;
return;
}

来看看空间压缩：显然i层仅由i-1层转移，再看下转移方向，比如我们现在要算[i,j]则显然发现会用到[i-1,1~j]这些数据，这不就和01背包的空间压缩很像了吗！所以提示我们为了保证有用的旧数据保留着不被更新，等用完他再更新的情况下，我们就需要从n到1这样倒着去枚举啦

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<malloc.h>
#include<numeric>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
int main()
{
long long dp[2010] = { 0 };
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)dp[i] = 1;//初始化dp数组，所有仅含一个数的dp[][]值都是1
//从dp[2][]开始递推到dp[k][]
for(int i=2;i<=k;i++)
for (int j = n; j >= 1; j--)//dp[i][j],对于每个确定的i,j可以取1-n;
{
int x = 0;//细节：这个x是先存着答案！注意由于是计数，不像那种求min,max的dp,如果不用x暂存一下答案
//下面直接写dp[j]=dp[j]+dp[m]+dp[j/m]的话，会发现上一层的dp[j]多加了一次，也就是本来这一层算dp[j]应该从0开始累加的，但就造成了从dp[j]这个上一层的值开始累加了
for (int m = 1; m <= j / m; m++)//找j的约数
if (j % m == 0)
{
if (j / m != m)//约数不==，即若25的因数5,5总不能加两个dp[i][5]吧！
x = (x + dp[m] + dp[j / m]) % 1000000007;
else
x = (x + dp[m]) % 1000000007;//约数相等加其中一个便可
}
dp[j] = x;
//cout << dp[j] << endl;
}
int res = 0;
for (int i = 1; i <= n; i++)res = (res + dp[i]) % 1000000007;
cout << res;
return 0;
}