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

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-1i转移, 枚举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);}