题解 P2193 【HXY和序列】

Cripple_Abyss · 2020-07-06 22:53:16 · 题解

题目传送门

本题其实是一道基本的DP题，十分适合一些新手

DP三步法：

设计状态：

用 f_{i\ j}来表示符合条件的长度为 i ，最后一个数为 j 的序列个数
推状态转移方程：
```
f[i][j*k]=(f[i][j*k]+f[i-1][j])%mod
```
设定初值：
```
f[1][i]=1 
```

Code：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[2005][2005],ans;
int main() {
    cin>>n>>m;
    for (int i=1; i<=n; i++)
        f[1][i]=1;
    for (int i=2; i<=m; i++)
        for (int j=1; j<=n; j++)
            for (int k=1; k<=n/j; k++) 
                f[i][j*k]=(f[i][j*k]+f[i-1][j])%mod;
    for (int i=1; i<=n; i++) 
        ans=(ans+f[m][i])%mod;
    cout<<ans;
    return 0;
}

都看到这里了，点个赞呗QwQ