20181011 NOIP集训 Test1 – [题组/考试]


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

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 
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);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注