小团的装饰物
发布于2021-04-16
上次编辑2021-04-16
问题描述
小团正在装饰自己的书桌，他的书桌上从左到右有 m 个空位需要放上装饰物。商店中每个整数价格的装饰物恰好有一种，且每种装饰物的数量无限多。
小团去商店的时候，想到了一个购买方案，他要让右边的装饰物价格是左边的倍数。用数学语言来说，假设小团的 m 个装饰物价格为 a[1], a[2], ..., a[m] ，那么对于任意的 1≤i≤j≤m ，a[j] 是 a[i] 的倍数。
小团是一个节约的人，他希望最贵的装饰物不超过 n 元。现在，请你计算小团有多少种购买的方案？
格式：
输入：
- 输入包含两个数，n 和 m 。
输出：
- 输出一个数，结果对 998244353 取模，表示购买的方案数。
示例：
输入：4 2
输出：8
解释：[1,1][1,2][1,3][1,4][2,2][2,4][3,3][4,4] 共 8 种。
提示：
- 对于 40% 的数据，
n, m ≤ 10
- 对于 100% 的数据，
1 ≤ n, m ≤ 1000
解题思路
方法一：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, m, MOD = 998244353;
cin >> n >> m;
vector<int> dp(1 + n, 1);
while (--m) {
vector<int> tmp(1 + n);
for (int i = n; i >= 1; --i) {
for (int j = 1; i * j <= n; ++j) {
tmp[i * j] = (1LL * tmp[i * j] + dp[i]) % MOD;
}
}
swap(dp, tmp);
}
int ans = 0;
for (int x : dp) {
ans = (1LL * ans + x) % MOD;
}
cout << ans << '\n';
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, m, MOD = 998244353;
cin >> n >> m;
vector<vector<int>> fac(n + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j * j <= i; ++j) {
if (i % j == 0) {
fac[i].emplace_back(j);
if (j * j != i) {
fac[i].emplace_back(i / j);
}
}
}
}
vector<vector<int>> memo(n + 1, vector<int>(m + 1));
function<int(int, int)> dp = [&](int n, int m) {
if (memo[n][m]) {
return memo[n][m];
}
if (n == 1 || m == 1) {
return 1;
}
int res = 0;
for (int x : fac[n]) {
res = (1LL * res + dp(x, m - 1)) % MOD;
}
return (memo[n][m] = res);
};
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (1LL * ans + dp(i, m)) % MOD;
}
cout << ans << '\n';
return 0;
}
|
方法二：
实际上这道题来自 AtCoder C - Multiple Sequences，原题的范围是 \(1 \le N, M \le 2\times10^5\)。