题目描述
已知一个长度为l的序列：b1，b2，b3，…，bl (1<=b1<=b2<=b3<=…<=bl<=n)。若这个序列满足每个元素是它后续元素的因子，换句话说就是对于任意的i (2<=i<=l)都满足bi%bi-1=0 (其中“%”代表求余)，则称这个序列是完美的。你的任务是对于给定的n和l，计算出一共有多少序列是完美序列。由于答案很大，所有输出答案对1000000007取余后的结果。
输入
输入的第一行为一个正整数T (T<=1000)，代表一共有T组测试数据。
每组测试数据包含两个正整数n，l (1<=n, l<=2000)，分别代表序列中元素大小的最大值和序列的长度。
输出
对于每组测试数据，输出一行包含一个整数，代表答案对1000000007取余后的结果。
样例输入
3
3 2
6 4
2 1
样例输出
5
39
2
ps：
这个题目真的看了好久好久…
原来这是一个二维dp，但是题解都看得很费劲。
- 首先明确dp[i][j]表示长度为i，最后一个数为j的序列的种数
- bi%bi-1=0 （i-1）是下标，这句话的意思是，对于任意的i，前一个数是后一个数的因子
- 状态转移方程
dp[i+1][p]=dp[i+1][p]+dp[i][x];//p是x的倍数
打表
我们拿3 2举个例子，长度为2且最大值为3代表最大值可以为1 2 3，那么就有
下面都是符合3 2这组数据的
-
1 1
-
1 2
-
2 2
-
1 3
-
3 3
都是长度为2 ，且最大值为3，且前一个数是后一个数的因子，我们把它们结合起来就是 -
长度为2最大值为1，—— 2 1（1 1）
-
长度为2最大值为2，—— 2 2（1 2,2 2）
-
长度为2最大值为3，—— 2 3（1 3,3 3）
把它们加起来就是答案了
1+2+2=5
- 以6 4为例，值为a[6][4]+a[5][4]+a[4][4]+a[3][4]+a[2][4]+a[1][4]=16+4+10+4+4+1=39
- a[6][4]=a[5][4]+a[5][2]+a[5][1]
- 即a[i][j]为a[i-1][w]的和，w为j的因子
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e3 + 5;
ll dp[maxn][maxn];
int main()
{
int n, l, t;
for (int i = 1; i < maxn; ++i)
dp[1][i] = 1; //长度为1的都是只有一种
for (int i = 1; i < maxn - 1; ++i)
{
//因为下面的代码是从i+1开始的，为了防止溢出，这里就要减去1
for (int x = 1; x <= maxn; ++x)
{
for (int p = x; p < maxn; p += x) //p是x的倍数
dp[i + 1][p] = (dp[i + 1][p] + dp[i][x]) % 1000000007;
}
}
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &l);
int ans = 0;
for (int i = 1; i <= n; ++i)
ans = (ans + dp[l][i]) % 1000000007;
printf("%d\n", ans);
}
return 0;
}
| 没有在长夜痛哭过的人，不足以谈人生——歌德 |
|---|
京公网安备 11010502036488号