# Mashmokh and ACM Editorial | GeeksToCode

This is an editorial post of the code forces problem Mashmokh and ACM.

## Problem Statement

Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn’t able to solve them. That’s why he asked you to help him with these tasks. One of these tasks is the following.

A sequence of l integers b1, b2, …, bl (1 ≤ b1 ≤ b2 ≤ … ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all i (1 ≤ i ≤ l - 1).

Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).

## Input

The first line of input contains two space-separated integers n, k (1 ≤ n, k ≤ 2000).

## Output

a single integer — the number of good sequences of length k modulo 1000000007 (109 + 7).ExamplesInputCopy

`3 2`

Output

`5`

## Detailed Editorial

In the above problem, we have to find a number of k length good sequence from the array consisting of n integers (1, 2, …, n).

As per definition, a good sequence is a sequence where b(i+1)|b(i) for all (1 ≤ I ≤ l-1), where l is the length of the sequence.

The idea is that we will iterate the array (1, 2, .., n) from backward and check whether for element b(i-1) is a factor of b(i).

For example, in sequence [1,2,3], we will traverse from backward and check whether 2 is a factor of 3 or not.

For checking factors we can run an O(√n) loop to find it but finding factors for each element of the array will be too costly and will give TLE.

So, for resolving TLE, we will pre-compute the factors before, since constraints of n are (1 ≤ n ≤ 2000), we can afford pre-computing the factors before.

Later will recursively find k length good subsequence for every element of the array.

If we find a good sequence of length k, we will return 1 and we will continue it for every subsequence.

It will be a recursive solution which will be changed to memoized version of DP to pass all the given test under constraints. Also, don’t forget to represent your answer in modulo (1e9+7).

That’s it, hope the idea is clear. If you have any doubts ask it in the
comment section.

## Detailed Solution in C++

``````#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 1000000007

ll dp;
map<ll, set<ll>> mp;

ll F(ll n, ll k)
{
if(k == 1 || n == 1) return 1;
if(dp[n][k] != -1) return dp[n][k];

ll ans =((F(n, k-1) % mod) + (F(1, k-1) % mod) % mod);
for(auto i = mp[n].begin(); i != mp[n].end(); i++)
{
ll s = 0, x = *i;
if(n % x == 0 && x == n/x)
{
s = (F(x, k-1)) % mod;
}
else if(n % x == 0)
{
s = (F(x, k-1) % mod) + (F(n/x, k-1) % mod) % mod;
}
ans = ((ans % mod) + (s % mod) % mod);
}
return dp[n][k] = ans % mod;
}

int32_t main()
{
ll t = 1;

while(t--)
{
ll n, k;
cin >> n >> k;

for(ll i = 2; i <= 2000; i++)
{
for(ll j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
{
mp[i].insert(j);
}
}
}

memset(dp, -1, sizeof(dp));

ll s = 0;
for(ll i = n; i >= 1; i--)
{
s = (s % mod + F(i, k) % mod) % mod;
}
cout<<(s % mod)<<"\n";
}
return 0;
}``````

Practice one more DP problem