题目文件(吉大附中内部资料)

T1 Simple – [DP]

题解 :

状态 :

$F[i][j]$代表确定了前$i$位, 最后一位为$j$的方案数

转移 :

$F[i][j]=\sum\limits_{k|j}F[i-1][k]$, 复杂度$O(N\times M\sqrt M)$

优化 :

枚举约数浪费了相当多的时间, 我们从$i-1$向$i$转移, 枚举$j$的倍数即可.

$F[i+1][k] += F[i][j], j|k$

由于恰好枚举了所有约数, 复杂度是$O(N\times M\ln M)$的, 可过本题

关于恰好枚举$1\sim N$所有约数是$O(N\ln N)$的, 有一个类似于调和级数的计算方法, 知道就好

代码 :

#include <cstdio>const int p = 1e9+7;int f[1100][1100], ans;int main() { freopen("Simple.in", "r", stdin); freopen("Simple.out", "w", stdout); int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++ ) f[1][i] = 1; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) for(int k = j; k <= m; k +=j) f[i+1][k] = (f[i+1][k]+f[i][j])%p; for(int i = 1; i <= m; i ++ ) ans = (ans+f[n][i])%p; printf("%d\n", ans);}