题解 [email protected]洛谷 | [email protected] 【Mashmokh and ACM】

一道小清新动规题。

题意:求长度为 kk 的、最大数不超过 nn 的数列,满足 ai=ai1×mula_i=a_{i-1}\times mul2in2\le i\le nmulmul 为正整数)。


思路:

容易想到设计状态 dpi,jdp_{i,j} 表示长度为 ii 时最大数为 jj 的方案总数。

转移方程也比较好想,根据数列要求,枚举所有可能的倍数,加上对应方案的 dpdp 值即可。即:dpi,j=k 是 j 的因数dpi1,kdp_{i,j}=\displaystyle\sum_{k\ \text{是}\ j\ \text{的因数}}dp_{i-1,k}。由于因数不好统计,我们根据 i,ki,k 来反推即可。

但是还没有结束,虽然我们可以通过此题,但是作为一个优(du)秀(liu)的 OIer,你不觉得 dpdp 数组这么大很多余吗?我们对于每一个 ii,只用到了 i1i-1dpdp 值,显然可以压缩空间啊!

考虑将 dpjdp_j 定义为最大数为 jj 的方案总数,原本的 ii 是没有必要存的。转移方程也没有特别大的变化。


代码:

//By: [email protected]_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;
}