题解 CF414B 【Mashmokh and ACM】

· · 题解

题解 CF414B 【Mashmokh and ACM】

看到大家都是直接递推的，我来一个记忆化搜索的方法

本题可以看成一个简单的数位dp，对于数位dp，我们一般采用记忆化搜索，这样对于一些复杂的问题能更方便地解决。。

当然了，这道题还是比较基础的，连前导0之类的都不用判断，普通递推也是非常好的

设 f_{i,j} 为当前是第i个位置，这一位数是j的状态数

那么可以推出递推式：

f_{i,j} = \sum_{k \ \text{是}\ j\ \text{的因数}} f_{i-1,k}

上代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9+7;
int n,k;
ll f[2005][2005];
ll dfs(int pos,int statu)
{
    if(pos == 0) return 1;
    if(f[pos][statu]) return f[pos][statu];
    ll ans = 0;
    for(int i = statu;i <= n;i+=statu)
    {
        (ans += dfs(pos-1,i))%=mod;
    }
    return f[pos][statu] = ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    ll anss = dfs(k,1);
    printf("%lld",anss);
    return 0;
}