Recuento de arrays distintas de tamaño N con elementos hasta K, de modo que el par de elementos adyacentes sea ascendente o no múltiplo

Posted on by Rudeus Greyrat

Dados dos enteros N y K , encuentre el número distinto de formas de crear una array de N elementos donde cada elemento está en el rango [1, K] y cada par de elementos adyacentes (P, Q) es tal que P <= Q o P % Q > 0 .

Ejemplo:

Entrada: N = 2, K = 3
Salida: 7
Explicación: Las arrays que satisfacen las condiciones dadas son {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3 }, {3, 3}, {3, 2}.

Entrada: N = 9, K = 1
Salida: 1
Explicación: Las únicas arrays que satisfacen las condiciones dadas son {1, 1, 1, 1, 1, 1, 1, 1, 1}.

Enfoque: El problema dado se puede resolver usando Programación Dinámica basada en las siguientes observaciones:

  • Considere una array 2D, digamos dp[][] donde dp[x][y] representa el recuento de arrays de longitud x que tienen y como su último elemento.
  • Ahora, la cantidad de formas de crear una array de longitud x que tenga y como su último elemento y que tenga todos los elementos de la array en el rango [1, K] es la suma de las formas de crear una array de longitud (y – 1) que tenga la último elemento sobre el rango [1, K] y se puede representar como relación  dp[x][y] = \sum_{j=1}^{j = k} dp[x-1][j] .
  • Los únicos casos donde P <= Q o P % Q > 0 se considerarán donde (P, Q) son el par de elementos adyacentes. La array que no satisface ninguna de estas condiciones se puede restar de cada estado usando la relación  dp[x][y] = \sum_{j=1}^{j = k} dp[x-1][j]  are donde y % j = 0 .

A partir de las observaciones anteriores, calcule la tabla dp[][] e imprima el valor de dp[N][K] como el recuento resultante de arrays formadas. Siga los pasos a continuación para resolver el problema dado:

  • Almacene todos los divisores de todos los enteros sobre el rango [1, K] usando el enfoque en Sieve of Eratosthenes en una array, digamos divisor[][] .
  • Inicialice una array 2D , digamos dp[][] de dimensión (N + 1)*(K + 1) tal que dp[x][y] representa el recuento de arrays de longitud x que tienen y como su último elemento.
  • Inicialice un dp[1][j] a 1 como el número de formas de crear una array de tamaño 1 que tenga cualquier elemento j como su último elemento es 1 .
  • Iterar sobre el rango [2, N] usando la variable x y realizar los siguientes pasos:
    • Para cada valor posible de j sobre el rango [1, K], incremente el valor de dp[x][y] en dp[x – 1][j] .
    • Itere sobre el rango [1, K] usando el valor de y y para cada divisor, digamos D de y disminuya el valor de dp[x][y] por dp[x – 1][D] ya que esto no satisface casos donde P <= Q o P % Q > 0 para todos los pares de elementos adyacentes (P, Q) .
  • Después de completar los pasos anteriores, imprima el valor de  \sum_{j=1}^{j = k} dp[N][j]  como resultado.

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of distinct
// arrays of size n having elements in
// range [1, k] and all adjacent elements
// (P, Q) follows (P <= Q) or (P % Q > 0)
int countArrays(int n, int k)
{
    // Stores the divisors of all
    // integers in the range [1, k]
    vector<vector<int> > divisors(k + 1);
 
    // Calculate the divisors of all
    // integers using the Sieve
    for (int i = 1; i <= k; i++) {
        for (int j = 2 * i; j <= k; j += i) {
            divisors[j].push_back(i);
        }
    }
 
    // Stores the dp states such that
    // dp[i][j] with i elements having
    // j as the last element of array
    vector<vector<int> > dp(
        n + 1, vector<int>(k + 1));
 
    // Initialize the dp array
    for (int j = 1; j <= k; j++) {
        dp[1][j] = 1;
    }
 
    // Calculate the dp states using the
    // derived relation
    for (int x = 2; x <= n; x++) {
 
        // Calculate the sum for len-1
        int sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += dp[x - 1][j];
        }
 
        // Subtract dp[len-1][j] for each
        // factor of j from [1, K]
        for (int y = 1; y <= k; y++) {
            dp[x][y] = sum;
            for (int d : divisors[y]) {
                dp[x][y] = (dp[x][y] - dp[x - 1][d]);
            }
        }
    }
 
    // Calculate the final result
    int sum = 0;
    for (int j = 1; j <= k; j++) {
        sum += dp[n][j];
    }
 
    // Return the resultant sum
    return sum;
}
 
// Driver Code
int main()
{
    int N = 2, K = 3;
    cout << countArrays(N, K);
 
    return 0;
}

Java

// Java program of the above approach
 
import java.util.*;
 
class GFG{
 
// Function to find the count of distinct
// arrays of size n having elements in
// range [1, k] and all adjacent elements
// (P, Q) follows (P <= Q) or (P % Q > 0)
static int countArrays(int n, int k)
{
    // Stores the divisors of all
    // integers in the range [1, k]
    Vector<Integer> []divisors = new Vector[k + 1];
    for (int i = 0; i < divisors.length; i++)
        divisors[i] = new Vector<Integer>();
 
    // Calculate the divisors of all
    // integers using the Sieve
    for (int i = 1; i <= k; i++) {
        for (int j = 2 * i; j <= k; j += i) {
            divisors[j].add(i);
        }
    }
 
    // Stores the dp states such that
    // dp[i][j] with i elements having
    // j as the last element of array
    int [][] dp = new int[n + 1][k + 1];
 
    // Initialize the dp array
    for (int j = 1; j <= k; j++) {
        dp[1][j] = 1;
    }
 
    // Calculate the dp states using the
    // derived relation
    for (int x = 2; x <= n; x++) {
 
        // Calculate the sum for len-1
        int sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += dp[x - 1][j];
        }
 
        // Subtract dp[len-1][j] for each
        // factor of j from [1, K]
        for (int y = 1; y <= k; y++) {
            dp[x][y] = sum;
            for (int d : divisors[y]) {
                dp[x][y] = (dp[x][y] - dp[x - 1][d]);
            }
        }
    }
 
    // Calculate the final result
    int sum = 0;
    for (int j = 1; j <= k; j++) {
        sum += dp[n][j];
    }
 
    // Return the resultant sum
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2, K = 3;
    System.out.print(countArrays(N, K));
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program of the above approach
 
# Function to find the count of distinct
# arrays of size n having elements in
# range [1, k] and all adjacent elements
# (P, Q) follows (P <= Q) or (P % Q > 0)
def countArrays(n, k):
   
    # Stores the divisors of all
    # integers in the range [1, k]
    divisors = [[] for i in range(k + 1)]
 
    # Calculate the divisors of all
    # integers using the Sieve
    for i in range(1, k + 1, 1):
        for j in range(2 * i, k + 1, i):
            divisors[j].append(i)
 
    # Stores the dp states such that
    # dp[i][j] with i elements having
    # j as the last element of array
    dp = [[0 for i in range(k+1)] for j in range(n + 1)]
 
    # Initialize the dp array
    for j in range(1, k + 1, 1):
        dp[1][j] = 1
 
    # Calculate the dp states using the
    # derived relation
    for x in range(2, n + 1, 1):
        # Calculate the sum for len-1
        sum = 0
        for j in range(1, k + 1, 1):
            sum += dp[x - 1][j]
 
        # Subtract dp[len-1][j] for each
        # factor of j from [1, K]
        for y in range(1, k + 1, 1):
            dp[x][y] = sum
            for d in divisors[y]:
                dp[x][y] = (dp[x][y] - dp[x - 1][d])
 
    # Calculate the final result
    sum = 0
    for j in range(1, k + 1, 1):
        sum += dp[n][j]
 
    # Return the resultant sum
    return sum
 
# Driver Code
if __name__ == '__main__':
    N = 2
    K = 3
    print(countArrays(N, K))
     
    # This code is contributed by ipg2016107.

C#

// C# program for the approach
using System;
using System.Collections.Generic;
 
class GFG {
 
// Function to find the count of distinct
// arrays of size n having elements in
// range [1, k] and all adjacent elements
// (P, Q) follows (P <= Q) or (P % Q > 0)
static int countArrays(int n, int k)
{
    // Stores the divisors of all
    // integers in the range [1, k]
    List<int> []divisors = new List<int>[k + 1];
 
    for (int i = 0; i < divisors.Length; i++)
        divisors[i] = new List<int>();
 
    // Calculate the divisors of all
    // integers using the Sieve
    for (int i = 1; i <= k; i++) {
        for (int j = 2 * i; j <= k; j += i) {
            divisors[j].Add(i);
        }
    }
 
    // Stores the dp states such that
    // dp[i][j] with i elements having
    // j as the last element of array
    int [,] dp = new int[n + 1, k + 1];
 
    // Initialize the dp array
    for (int j = 1; j <= k; j++) {
        dp[1, j] = 1;
    }
     
    int sum;
 
    // Calculate the dp states using the
    // derived relation
    for (int x = 2; x <= n; x++) {
 
        // Calculate the sum for len-1
        sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += dp[x - 1, j];
        }
 
        // Subtract dp[len-1][j] for each
        // factor of j from [1, K]
        for (int y = 1; y <= k; y++) {
            dp[x, y] = sum;
            foreach (int d in divisors[y]) {
                dp[x, y] = (dp[x, y] - dp[x - 1, d]);
            }
        }
    }
 
    // Calculate the final result
    sum = 0;
    for (int j = 1; j <= k; j++) {
        sum += dp[n, j];
    }
 
    // Return the resultant sum
    return sum;
}
 
    // Driver Code
    public static void Main()
    {
        int N = 2, K = 3;
        Console.Write(countArrays(N, K));
    }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the count of distinct
        // arrays of size n having elements in
        // range [1, k] and all adjacent elements
        // (P, Q) follows (P <= Q) or (P % Q > 0)
        function countArrays(n, k)
        {
         
            // Stores the divisors of all
            // integers in the range [1, k]
            let divisors = new Array(k + 1).fill(new Array());
 
            // Calculate the divisors of all
            // integers using the Sieve
            for (let i = 1; i <= k; i++) {
                for (let j = 2 * i; j <= k; j += i) {
                    divisors[j].push(i);
                }
            }
 
            // Stores the dp states such that
            // dp[i][j] with i elements having
            // j as the last element of array
            let dp = new Array(n + 1).fill(new Array(k + 1));
 
            // Initialize the dp array
            for (let j = 1; j <= k; j++) {
                dp[1][j] = 1;
            }
 
            // Calculate the dp states using the
            // derived relation
            for (let x = 2; x <= n; x++) {
 
                // Calculate the sum for len-1
                let sum = 0;
                for (let j = 1; j <= k; j++) {
                    sum += dp[x - 1][j];
                }
 
                // Subtract dp[len-1][j] for each
                // factor of j from [1, K]
                for (let y = 1; y <= k; y++) {
                    dp[x][y] = sum;
                    for (let d of divisors[y]) {
                        dp[x][y] = (dp[x][y] - dp[x - 1][d]);
                    }
                }
            }
 
            // Calculate the final result
            let sum = 0;
            for (let j = 1; j <= k; j++) {
                sum += dp[n][j];
            }
            sum++;
             
            // Return the resultant sum
            return sum;
        }
 
        // Driver Code
        let N = 2, K = 3;
        document.write(countArrays(N, K));
 
// This code is contributed by Potta Lokesh
    </script>
Producción

7

Complejidad de tiempo: O(N*K*log K) 
Espacio auxiliar:  O(K*log K)

Publicación traducida automáticamente

Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *