wish_me's blog

Count of arrays in which all adjacent elements are such that one of them divide the another
By wish_me, history, 7 years ago, In English

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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the value of the m is small, there's an O(m^3 * logn) solution using matrix exponentiation.Can you explain please?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      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.

      → Reply