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[2001][2001];
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

Leave a Comment

Your email address will not be published. Required fields are marked *