Given two positive integer n and n. The task is to find the number of arrays of size n that can be formed such that :
Each element is in range [1, m]
All adjacent element are such that one of them divide the another i.e element Ai divides Ai + 1 or Ai + 1 divides Ai + 2.
Examples:
Input : n = 3, m = 3.
Output : 17
{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1},
{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},
{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},
{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1},
{3,3,3} are possible arrays.
Input : n = 1, m = 10.
Output : 10
can any one help me in this interesting dp problem?
dp[index included][number], dp[0][1] = 1, dp[0][x] = 0.
dp[i][num] = sum for each divisor of num {dp[i — 1][divisor]} + sum for each k > 1 {dp[i — 1][k * num]}
This is O(n * m * log(m)), sum for each 1 <= i <= m of d[n][i] is the answer. If the value of the m is small, there's an O(m^3 * logn) solution using matrix exponentiation.
If the value of the m is small, there's an O(m^3 * logn) solution using matrix exponentiation.Can you explain please?
This dp is a simple linear recursive relation. Create a m x m square matrix (one based rows/columns) where
if i % j == 0 or j % i == 0, matrix[i][j] = 1
else matrix[i][j] = 0
if you multiply matrix by a column matrix (starting with (1, 0, 0, 0, 0)), you get the next row of the dp. Since you need to multiply it by matrix n times and multiplication is comutative, you can use fast exponentiation to get matrix^n.