题解 CF414B 【Mashmokh and ACM】
rui_er
2020-09-02 18:51:31
一道小清新动规题。
题意：求长度为 $k$ 的、最大数不超过 $n$ 的数列，满足 $a_i=a_{i-1}\times mul$（$2\le i\le n$ 且 $mul$ 为正整数）。
---
思路：
容易想到设计状态 $dp_{i,j}$ 表示长度为 $i$ 时最大数为 $j$ 的方案总数。
转移方程也比较好想，根据数列要求，枚举所有可能的倍数，加上对应方案的 $dp$ 值即可。即：$dp_{i,j}=\displaystyle\sum_{k\ \text{是}\ j\ \text{的因数}}dp_{i-1,k}$。由于因数不好统计，我们根据 $i,k$ 来反推即可。
但是还没有结束，虽然我们可以通过此题，但是作为一个优（du）秀（liu）的 OIer，你不觉得 $dp$ 数组这么大很多余吗？我们对于每一个 $i$，只用到了 $i-1$ 的 $dp$ 值，显然可以压缩空间啊！
考虑将 $dp_j$ 定义为最大数为 $j$ 的方案总数，原本的 $i$ 是没有必要存的。转移方程也没有特别大的变化。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2005, mod = 1e9+7;
ll n, k;
ll dp[N], tmp[N], ans;
int main() {
scanf("%lld%lld", &n, &k);
for(ll i=1;i<=n;i++) dp[i] = 1;
for(ll cnts=2;cnts<=k;cnts++) {
for(ll i=1;i<=n;i++) tmp[i] = 0;
for(ll i=1;i<=n;i++) {
for(ll j=1,_=i*j;_<=n;j++,_=i*j) tmp[_] = (tmp[_] + dp[i]) % mod;
}
for(ll i=1;i<=n;i++) dp[i] = tmp[i];
}
for(ll i=1;i<=n;i++) ans = (ans + dp[i]) % mod;
printf("%lld\n", ans);
return 0;
}
```