Contar secuencias de enteros positivos que tengan el producto X

Dada una array arr[] de tamaño N , la tarea es encontrar el número total de secuencias de enteros positivos posibles (mayores que 1) cuyo producto sea exactamente X. El valor de X se calcula como el producto de los términos, donde el i ^-ésimo término se genera elevando el i ^-ésimo número primo a la potencia de arr[i] .

X = 2 ^ arr[1] * 3 ^ arr[2] * 5 ^ arr[3] * 7 ^ arr[4] * 11 ^ arr[5] * … hasta el enésimo término

Nota: Como el número total de tales secuencias puede ser muy grande, imprima la respuesta módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: arr[] = {1, 1}
Salida: 3
Explicación:
Aquí, X = 2^1 * 3^1 = 6
Posibles secuencias positivas cuyo producto es X: {2, 3}, {3, 2}, { 6}

Entrada: arr[] = {2}
Salida: 2
Explicación:
Aquí, X = 2^2 = 4.
Posibles secuencias positivas cuyo producto es X: {2, 2} y {4}.

Enfoque ingenuo: la idea es calcular primero el valor de X y luego generar todas las secuencias posibles cuyo producto sea X usando recursividad .

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: este problema se puede resolver utilizando la programación dinámica y el enfoque combinatorio . A continuación se muestran los pasos:

Primero, encuentre el número máximo de elementos positivos que pueden aparecer en todas las secuencias posibles que serán la suma de la array dada arr[] .
Luego use la programación dinámica para llenar los espacios en las posibles secuencias comenzando con el índice i desde 1 hasta la longitud de la secuencia.
- Para cada j-ésimo número primo que tenga el valor P[j] , divida todos los números primos P[j] en cada una de las ranuras i.
- Utilice el enfoque combinatorio para dividir los elementos P[j] en ranuras i. Almacene el valor en la arrayways [] de modo queways[i] se actualice de la siguiente manera:

$ways[i] \space *= \dbinom {P[j] + i - 1}{i - 1}$

Número de formas de dividir N elementos idénticos en K ranuras = (N + K – 1)C(K – 1)
Este enfoque también se conoce formalmente como enfoque de estrellas y barras en combinatoria.

Para cada uno de los j primos, multiplique los valores como se muestra en la multiplicación.
Sin embargo, ways[] también contendrá las secuencias con una o más ranuras vacías, por lo tanto, reste la contribución exacta de todas las ranuras donde el número de ranuras ocupadas es menor que i.
Para cada una de las ranuras de j = 1 a i – 1 , seleccione j ranuras de i y reste su contribución.

$ways[i] \space -= \dbinom{i}{j} * ways[j]$

Finalmente, agregue todos los valores de la arrayways [] para obtener el resultado total.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int bin[3000][3000];
 
// Function to print the total number
// of possible sequences with
// product X
void countWays(const vector<int>& arr)
{
    int mod = 1e9 + 7;
    bin[0][0] = 1;
 
    // Precomputation of
    // binomial coefficients
    for (int i = 1; i < 3000; i++) {
        bin[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            bin[i][j] = (bin[i - 1][j]
                         + bin[i - 1][j - 1])
                        % mod;
        }
    }
 
    // Max length of a subsequence
    int n = 0;
    for (auto x : arr)
        n += x;
 
    // Ways dp array
    vector<int> ways(n + 1);
 
    for (int i = 1; i <= n; i++) {
        ways[i] = 1;
 
        // Fill i slots using all
        // the primes
        for (int j = 0;
             j < (int)arr.size(); j++) {
            ways[i] = (ways[i]
                       * bin[arr[j] + i - 1]
                            [i - 1])
                      % mod;
        }
 
        // Subtract ways for all
        // slots that exactly
        // fill less than i slots
        for (int j = 1; j < i; j++) {
            ways[i] = ((ways[i]
                        - bin[i][j] * ways[j])
                           % mod
                       + mod)
                      % mod;
        }
    }
 
    // Total possible sequences
    int ans = 0;
    for (auto x : ways)
        ans = (ans + x) % mod;
 
    // Print the resultant count
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 1 };
 
    // Function call
    countWays(arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static int [][]bin = new int[3000][3000];
 
// Function to print the total number
// of possible sequences with
// product X
static void countWays(int[] arr)
{
    int mod = (int)1e9 + 7;
    bin[0][0] = 1;
 
    // Precomputation of
    // binomial coefficients
    for(int i = 1; i < 3000; i++)
    {
        bin[i][0] = 1;
        for(int j = 1; j <= i; j++)
        {
            bin[i][j] = (bin[i - 1][j] +
                         bin[i - 1][j - 1]) % mod;
        }
    }
 
    // Max length of a subsequence
    int n = 0;
    for(int x : arr)
        n += x;
 
    // Ways dp array
    int[] ways = new int[n + 1];
 
    for(int i = 1; i <= n; i++)
    {
        ways[i] = 1;
 
        // Fill i slots using all
        // the primes
        for(int j = 0; j < arr.length; j++)
        {
            ways[i] = (ways[i] *
                    bin[arr[j] + i - 1][i - 1]) % mod;
        }
 
        // Subtract ways for all
        // slots that exactly
        // fill less than i slots
        for(int j = 1; j < i; j++)
        {
            ways[i] = ((ways[i] - bin[i][j] *
                        ways[j]) % mod + mod) % mod;
        }
    }
 
    // Total possible sequences
    int ans = 0;
    for(int x : ways)
        ans = (ans + x) % mod;
 
    // Print the resultant count
    System.out.print(ans + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 1 };
 
    // Function call
    countWays(arr);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
bin = [[0 for i in range(3000)]
          for i in range(3000)]
 
# Function to print the total number
# of possible sequences with
# product X
def countWays(arr):
     
    mod = 10**9 + 7
    bin[0][0] = 1
 
    # Precomputation of
    # binomial coefficients
    for i in range(1, 3000):
        bin[i][0] = 1
         
        for j in range(1, i + 1):
            bin[i][j] = (bin[i - 1][j] +
                         bin[i - 1][j - 1]) % mod
 
    # Max length of a subsequence
    n = 0
     
    for x in arr:
        n += x
 
    # Ways dp array
    ways = [0] * (n + 1)
 
    for i in range(1, n + 1):
        ways[i] = 1
 
        # Fill i slots using all
        # the primes
        for j in range(len(arr)):
            ways[i] = (ways[i] *
                    bin[arr[j] + i - 1][i - 1]) % mod
 
        # Subtract ways for all
        # slots that exactly
        # fill less than i slots
        for j in range(1, i):
            ways[i] = ((ways[i] - bin[i][j] *
                        ways[j]) % mod + mod) % mod
 
    # Total possible sequences
    ans = 0
     
    for x in ways:
        ans = (ans + x) % mod
 
    # Print the resultant count
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 1 ]
 
    # Function call
    countWays(arr)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
static int [,]bin = new int[3000, 3000];
 
// Function to print the total number
// of possible sequences with
// product X
static void countWays(int[] arr)
{
    int mod = (int)1e9 + 7;
    bin[0, 0] = 1;
 
    // Precomputation of
    // binomial coefficients
    for(int i = 1; i < 3000; i++)
    {
        bin[i, 0] = 1;
        for(int j = 1; j <= i; j++)
        {
            bin[i, j] = (bin[i - 1, j] +
                         bin[i - 1, j - 1]) % mod;
        }
    }
 
    // Max length of a subsequence
    int n = 0;
    foreach(int x in arr)
        n += x;
 
    // Ways dp array
    int[] ways = new int[n + 1];
 
    for(int i = 1; i <= n; i++)
    {
        ways[i] = 1;
 
        // Fill i slots using all
        // the primes
        for(int j = 0; j < arr.Length; j++)
        {
            ways[i] = (ways[i] *
                    bin[arr[j] + i - 1, i - 1]) % mod;
        }
 
        // Subtract ways for all
        // slots that exactly
        // fill less than i slots
        for(int j = 1; j < i; j++)
        {
            ways[i] = ((ways[i] - bin[i, j] *
                        ways[j]) % mod + mod) % mod;
        }
    }
 
    // Total possible sequences
    int ans = 0;
    foreach(int x in ways)
        ans = (ans + x) % mod;
 
    // Print the resultant count
    Console.Write(ans + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int[] arr = { 1, 1 };
 
    // Function call
    countWays(arr);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach
 
var bin = Array.from(Array(3000), ()=> Array(3000).fill(0));
 
// Function to print the total number
// of possible sequences with
// product X
function countWays(arr)
{
    var mod = 1000000007;
    bin[0][0] = 1;
 
    // Precomputation of
    // binomial coefficients
    for (var i = 1; i < 3000; i++) {
        bin[i][0] = 1;
        for (var j = 1; j <= i; j++) {
            bin[i][j] = (bin[i - 1][j]
                         + bin[i - 1][j - 1])
                        % mod;
        }
    }
 
    // Max length of a subsequence
    var n = 0;
    for (var x =0; x<arr.length; x++)
        n += arr[x];
 
    // Ways dp array
    var ways = Array(n + 1).fill(0);
 
    for (var i = 1; i <= n; i++) {
        ways[i] = 1;
 
        // Fill i slots using all
        // the primes
        for (var j = 0;
             j <arr.length; j++) {
            ways[i] = (ways[i]
                       * bin[arr[j] + i - 1]
                            [i - 1])
                      % mod;
        }
 
        // Subtract ways for all
        // slots that exactly
        // fill less than i slots
        for (var j = 1; j < i; j++) {
            ways[i] = ((ways[i]
                        - bin[i][j] * ways[j])
                           % mod
                       + mod)
                      % mod;
        }
    }
 
    // Total possible sequences
    var ans = 0;
    for (var i = 1; i <= n; i++)
        ans = (ans + ways[i]) % mod;
 
    // Print the resultant count
    document.write( ans );
}
 
// Driver Code
var arr = [ 1, 1 ];
// Function call
countWays(arr);
 
</script>

Producción

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta