Recuento de arrays en las que todos los elementos adyacentes son tales que uno de ellos divide al otro

Dados dos enteros positivos n y n . La tarea es encontrar el número de arreglos de tamaño n que se pueden formar de tal manera que: 

1. Cada elemento está en el rango [1, m]
2. Todos los elementos adyacentes son tales que uno de ellos divide al otro, es decir, el elemento A _i divide a A _{i + 1} o A _{i + 1} divide a A _{i + 2} .

Ejemplos:  

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 

Intentamos encontrar el número de valores posibles en cada índice de la array. Primero, en el índice 0 todos los valores son posibles desde 1 hasta m. Ahora observe para cada índice, podemos llegar a su múltiplo oa su factor. Entonces, precalcule eso y guárdelo para todos los elementos. Por lo tanto, para cada posición i, que termina en un número entero x, podemos ir a la siguiente posición i + 1, con el arreglo que termina en un número entero con múltiplo de x o factor de x. Además, el múltiplo de x o factor de x debe ser menor que m. 

Entonces, definimos una array 2D dp[i][j], que es el número de posibles arrays (elemento adyacente divisible) de tamaño i con j como su primer elemento de índice.  

1 <= i <= m, dp[1][m] = 1.
for 1 <= j <= m and 2 <= i <= n
  dp[i][j] = dp[i-1][j] + number of factor 
             of previous element less than m 
             + number of multiples of previous
             element less than m.

A continuación se muestra la implementación de este enfoque: 

// C++ program to count number of arrays
// of size n such that every element is
// in range [1, m] and adjacent are
// divisible
#include <bits/stdc++.h>
#define  MAX 1000
using namespace std;
 
int numofArray(int n, int m)
{
    int dp[MAX][MAX];
 
    // For storing factors.
    vector<int> di[MAX];
 
    // For storing multiples.
    vector<int> mu[MAX];
 
    memset(dp, 0, sizeof dp);
    memset(di, 0, sizeof di);
    memset(mu, 0, sizeof mu);
 
    // calculating the factors and multiples
    // of elements [1...m].
    for (int i = 1; i <= m; i++)
    {
        for (int j = 2*i; j <= m; j += i)
        {
            di[j].push_back(i);
            mu[i].push_back(j);
        }
        di[i].push_back(i);
    }
 
    // Initialising for size 1 array for
    // each i <= m.
    for (int i = 1; i <= m; i++)
        dp[1][i] = 1;
 
    // Calculating the number of array possible
    // of size i and starting with j.
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = 0;
 
            // For all previous possible values.
            // Adding number of factors.
            for (auto x:di[j])
                dp[i][j] += dp[i-1][x];
 
            // Adding number of multiple.
            for (auto x:mu[j])
                dp[i][j] += dp[i-1][x];
        }
    }
 
    // Calculating the total count of array
    // which start from [1...m].
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        ans += dp[n][i];
        di[i].clear();
        mu[i].clear();
    }
 
    return ans;
}
 
// Driven Program
int main()
{
    int n = 3, m = 3;
    cout << numofArray(n, m) << "\n";
    return 0;
}

// Java program to count number of arrays
// of size n such that every element is
// in range [1, m] and adjacent are
// divisible
import java.util.*;
 
class GFG
{
static int MAX = 1000;
 
static int numofArray(int n, int m)
{
    int [][]dp = new int[MAX][MAX];
 
    // For storing factors.
    Vector<Integer> []di = new Vector[MAX];
 
    // For storing multiples.
    Vector<Integer> []mu = new Vector[MAX];
 
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < MAX; j++)
        {
            dp[i][j] = 0;
        }
    }
    for(int i = 0; i < MAX; i++)
    {
        di[i] = new Vector<>();
        mu[i] = new Vector<>();
    }
     
    // calculating the factors and multiples
    // of elements [1...m].
    for (int i = 1; i <= m; i++)
    {
        for (int j = 2 * i; j <= m; j += i)
        {
            di[j].add(i);
            mu[i].add(j);
        }
        di[i].add(i);
    }
 
    // Initialising for size 1 array for
    // each i <= m.
    for (int i = 1; i <= m; i++)
        dp[1][i] = 1;
 
    // Calculating the number of array possible
    // of size i and starting with j.
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = 0;
 
            // For all previous possible values.
            // Adding number of factors.
            for (Integer x:di[j])
                dp[i][j] += dp[i - 1][x];
 
            // Adding number of multiple.
            for (Integer x:mu[j])
                dp[i][j] += dp[i - 1][x];
        }
    }
 
    // Calculating the total count of array
    // which start from [1...m].
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        ans += dp[n][i];
        di[i].clear();
        mu[i].clear();
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 3, m = 3;
    System.out.println(numofArray(n, m));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to count the number of
# arrays of size n such that every element is
# in range [1, m] and adjacent are divisible
 
MAX = 1000
 
def numofArray(n, m):
  
    dp = [[0 for i in range(MAX)] for j in range(MAX)]
 
    # For storing factors.
    di = [[] for i in range(MAX)]
 
    # For storing multiples.
    mu = [[] for i in range(MAX)]
 
    # calculating the factors and multiples
    # of elements [1...m].
    for i in range(1, m+1):
      
        for j in range(2*i, m+1, i):
          
            di[j].append(i)
            mu[i].append(j)
          
        di[i].append(i)
 
    # Initialising for size 1 array for each i <= m.
    for i in range(1, m+1):
        dp[1][i] = 1
 
    # Calculating the number of array possible
    # of size i and starting with j.
    for i in range(2, n+1):
      
        for j in range(1, m+1):
          
            dp[i][j] = 0
 
            # For all previous possible values.
            # Adding number of factors.
            for x in di[j]:
                dp[i][j] += dp[i-1][x]
 
            # Adding number of multiple.
            for x in mu[j]:
                dp[i][j] += dp[i-1][x]
          
    # Calculating the total count of array
    # which start from [1...m].
    ans = 0
    for i in range(1, m+1):
      
        ans += dp[n][i]
        di[i].clear()
        mu[i].clear()
     
    return ans
  
# Driven Program
if __name__ == "__main__":
  
    n = m = 3
    print(numofArray(n, m))
     
# This code is contributed by Rituraj Jain

// C# program to count number of arrays
// of size n such that every element is
// in range [1, m] and adjacent are
// divisible
using System;
using System.Collections.Generic;                
     
class GFG
{
static int MAX = 1000;
 
static int numofArray(int n, int m)
{
    int [,]dp = new int[MAX, MAX];
 
    // For storing factors.
    List<int> []di = new List<int>[MAX];
 
    // For storing multiples.
    List<int> []mu = new List<int>[MAX];
 
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < MAX; j++)
        {
            dp[i, j] = 0;
        }
    }
    for(int i = 0; i < MAX; i++)
    {
        di[i] = new List<int>();
        mu[i] = new List<int>();
    }
     
    // calculating the factors and multiples
    // of elements [1...m].
    for (int i = 1; i <= m; i++)
    {
        for (int j = 2 * i; j <= m; j += i)
        {
            di[j].Add(i);
            mu[i].Add(j);
        }
        di[i].Add(i);
    }
 
    // Initialising for size 1 array for
    // each i <= m.
    for (int i = 1; i <= m; i++)
        dp[1, i] = 1;
 
    // Calculating the number of array possible
    // of size i and starting with j.
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i, j] = 0;
 
            // For all previous possible values.
            // Adding number of factors.
            foreach (int x in di[j])
                dp[i, j] += dp[i - 1, x];
 
            // Adding number of multiple.
            foreach (int x in mu[j])
                dp[i, j] += dp[i - 1, x];
        }
    }
 
    // Calculating the total count of array
    // which start from [1...m].
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        ans += dp[n, i];
        di[i].Clear();
        mu[i].Clear();
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 3, m = 3;
    Console.WriteLine(numofArray(n, m));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program to count number of arrays
// of size n such that every element is
// in range [1, m] and adjacent are
// divisible
let MAX = 1000;
 
function numofArray(n, m)
{
    let dp = new Array(MAX);
  
    // For storing factors.
    let di = new Array(MAX);
  
    // For storing multiples.
    let mu = new Array(MAX);
  
    for(let i = 0; i < MAX; i++)
    {
        dp[i] = new Array(MAX);
        for(let j = 0; j < MAX; j++)
        {
            dp[i][j] = 0;
        }
    }
    for(let i = 0; i < MAX; i++)
    {
        di[i] = [];
        mu[i] = [];
    }
      
    // Calculating the factors and multiples
    // of elements [1...m].
    for(let i = 1; i <= m; i++)
    {
        for(let j = 2 * i; j <= m; j += i)
        {
            di[j].push(i);
            mu[i].push(j);
        }
        di[i].push(i);
    }
  
    // Initialising for size 1 array for
    // each i <= m.
    for(let i = 1; i <= m; i++)
        dp[1][i] = 1;
  
    // Calculating the number of array possible
    // of size i and starting with j.
    for(let i = 2; i <= n; i++)
    {
        for(let j = 1; j <= m; j++)
        {
            dp[i][j] = 0;
  
            // For all previous possible values.
            // Adding number of factors.
            for(let x = 0; x < di[j].length; x++)
                dp[i][j] += dp[i - 1][di[j][x]];
  
            // Adding number of multiple.
            for(let x = 0; x < mu[j].length; x++)
                dp[i][j] += dp[i - 1][mu[j][x]];
        }
    }
  
    // Calculating the total count of array
    // which start from [1...m].
    let ans = 0;
    for(let i = 1; i <= m; i++)
    {
        ans += dp[n][i];
        di[i] = [];
        mu[i] = [];
    }
    return ans;
}
 
// Driver Code
let n = 3, m = 3;
 
document.write(numofArray(n, m));
 
// This code is contributed by rag2127
 
</script>

17

Complejidad temporal: O(N*M).

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.