B. Mashmokh and ACM

素颜马尾好姑娘i 2022-08-26 14:24 22阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/414/B][http_codeforces.com_problemset_problem_414_B]

题意：就是给你一个n和k，让你用1 -- n这n个数，选出k个组成一个序列，这个序列满足任意后面一个都能够整除前面一个。求这个序列的个数、

分析：比赛的时候以为是数论的题目，直接分给搞数论的队友了，他说没有思路，我趁着电脑闲的打了一下表看看能不能发现点规律，但是没有，其实这道题目完全可以解决的。

记忆话深搜或者dp

由于其后面一个数是多少直接由他前面的数来决定，那么我们可以定义一个跟末尾数字有关的状态，dp\[ i \] \[ j \] 表示长度为 i 的序列最后一位是 j ，那么

状态转移方程：dp 【i】【j】 = sum（dp【i-1】【x】） x是j前面满足（j%x==0）的数。那么代码就很好写了。

可以直接打表缩短时间，但是cf是单组数据判题，下来时间反而长了。。。

感觉做题策略还是有问题，队长不称职！

代码：

#include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MOD=1000000007;
    const int N = 2002;
    int dp[2005][2005];
    int isit()
    {
        for(int i=1; i<=2002; i++)
            dp[1][i]=1;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                for (int z = j; z <= N; z+=j)
                {
                    dp[i][z] = (dp[i][z]+dp[i-1][j])%MOD;
                }
            }
        }
    }
    int main()
    {
        int n,k;
        isit();
        while(cin>>n>>k)
        {
            int ans = 0;
            for (int i = 1; i <= n; i++)
            {
                ans+=dp[k][i];
                ans%=MOD;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[http_codeforces.com_problemset_problem_414_B]: http://codeforces.com/problemset/problem/414/B