题目描述
给定 (N), (K),问有多少个长度为 (K) 的正整数序列满足相邻元素的乘积不超过 (N)。
正解
考虑递推,设 (f_{i,j}) 表示第 (i) 个位置填 (j) 的方案数。
然而值域实在太大,要将所有数存下来实在不太可行。
考虑有哪些状态本质上是相同的。
序列中一个元素 (a_i),可以转移到下一个位置 (a_{i + 1} leq lfloor N / a_i floor),发现 (lfloor N / a_i floor) 只有 (sqrt N) 种取值,可以直接记录下来。
那么将 (a_i le sqrt N),(a_i > sqrt N) 分别记录即可。
转移要用前缀和优化一下,实现的时候可以从大往小枚举记录前缀和 / 后缀和。
时间复杂度 (O(K sqrt N))
(color{DeepSkyBlue} {Code :})
#include <bits/stdc++.h>
#define N 105
#define V 31627
using namespace std;
const int mod = 1e9 + 7;
int n, K;
int f[N][V], g[N][V];
int cnt[V];
int main() {
scanf("%d %d", &K, &n);
int p = sqrt(K);
for(int i = 1; i < p; ++i)
cnt[i] = K / i - K / (i + 1);
cnt[p] = K / p - p;
for(int i = 1; i <= p; ++i) {
f[1][i] = 1;
g[1][i] = cnt[i];
}
for(int i = 1; i <= n; ++i) {
int sum = 0;
for(int j = 1; j <= p; ++j) {
sum = (sum + f[i][j]) % mod;
g[i + 1][j] = 1LL * sum * cnt[j] % mod;
}
for(int j = p; j >= 1; --j) {
sum = (sum + g[i][j]) % mod;
f[i + 1][j] = sum;
}
}
printf("%d
", f[n + 1][1]);
return 0;
}