Блог пользователя wish_me

Автор wish_me, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      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.