CodeForces 415D Mashmokh and ACM

时间：2023-01-07 13:16:15

$dp$。

记$dp[i][j]$表示已经放了$i$个数字，并且第$i$个数字放了$j$的方案数。那么$dp[i][j] = \sum\limits_{k|j}^{}  {dp[i - 1][k]}$。答案为$\sum\limits_{k=1}^{m}  {dp[n][k]}$

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c = getchar();

    x = ;

    while(!isdigit(c)) c = getchar();

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

}

const int maxn=;

LL dp[maxn][maxn],mod=1e9+;

int n,m;

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=;i<=m;i++) dp[][i]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            for(int k=j;k<=m;k=k+j)

            {

                dp[i+][k]=(dp[i+][k]+dp[i][j])%mod;

            }

        }

    }

    LL ans=;

    for(int i=;i<=m;i++) ans=(ans+dp[n][i])%mod;

    cout<<ans<<endl;

    return ;

}

相关文章