Count of divisible array
Given two positive integer n and m, find how many arrays of size n that can be formed such that:
- Each element of the array is in the range [1, m]
- Any adjacent element pair is divisible, i.e., that one of them divides another. Either element A[i] divides A[i + 1] or A[i + 1] divides A[i].
Input:
Only one line with two integer, n & m respectively.
Output:
Print number of different possible ways to create the array. Since the output could be long take modulo 10^9+7.
Constraints:
1<=n, m<=100
Example:
Input:
n = 3, m = 2.
Output:
8
Explanation:
{1,1,1},{1, 1, 2}, {1, 2, 1},
{1, 2, 2}, {2, 1, 1},
{2,1,2}, {2,2,1}, {2,2,2} are possible arrays.
Input:
n = 1, m = 5.
Output:
5
Explanation:
{1}, {2}, {3}, {4}, {5}
The above problem is a great example of recursion. What can be the recursive function and how we can formulate.
Say,
Let
F(n, m) = number of ways for array size n and range 1 to m
Now,
We actually can try picking every element from raging 1 to m and try recurring for other elements
So, the function can be written like:
So, to describe the arguments,
cur_index is your current index and the last element is the previous index value assigned. So basically need to check which value with range 1 to m fits in the cur_index such that the divisibility constraint satisfies.
So, to describe the body of the function
Now the above recursive function generates many overlapping sub-problem and that's why we use the top-down DP approach to store already computed sub-problem results.
Below is the implementation with adding memoization.
Initiate a 2D DP array with -1
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer