Consultas por el producto de los primeros N factoriales

Dadas las consultas Q[] donde cada consulta consta de un número entero N , la tarea es encontrar el producto de los primeros N factoriales para cada una de las consultas. Dado que el resultado podría ser grande, calcúlelo módulo 10 9 + 7 .
Ejemplos: 
 

Entrada: Q[] = {4, 5} 
Salida: 
288 
34560 
Consulta 1: 1! * 2! * 3! * 4! = 1 * 2 * 6 * 24 = 288 
Consulta 2: 1! * 2! * 3! * 4! * 5! = 1 * 2 * 6 * 24 * 120 = 34560
Entrada: Q[] = {500, 1000, 7890} 
Salida: 
976141892 
560688561 
793351288 
 

Enfoque: Cree dos arrays result[] y fact[] donde fact[i] almacenará el factorial de i y result[i] almacenará el producto del primer i factorial. 
Inicializa fact[0] = 1 y result[0] = 1 . Ahora para el resto de los valores, la relación de recurrencia será: 
 

hecho[i] = hecho[i – 1] * i 
resultado[i] = resultado[i – 1] * hecho[i] 
 

Ahora, cada consulta se puede responder utilizando la array result[] generada.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MAX 1000000
 
const ll MOD = 1e9 + 7;
 
// Declare result array globally
ll result[MAX + 1];
ll fact[MAX + 1];
 
// Function to precompute the product
// of factorials upto MAX
void preCompute()
{
 
    // Initialize base condition if n = 0
    // then factorial of 0 is equal to 1
    // and answer for n = 0 is 1
    fact[0] = 1;
    result[0] = 1;
 
    // Iterate loop from 1 to MAX
    for (int i = 1; i <= MAX; i++) {
 
        // factorial(i) = factorial(i - 1) * i
        fact[i] = ((fact[i - 1] % MOD) * i) % MOD;
 
        // Result for current n is equal to result[i-1]
        // multiplied by the factorial of i
        result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD;
    }
}
 
// Function to perform the queries
void performQueries(int q[], int n)
{
 
    // Precomputing the result till MAX
    preCompute();
 
    // Perform queries
    for (int i = 0; i < n; i++)
        cout << result[q[i]] << "\n";
}
 
// Driver code
int main()
{
 
    int q[] = { 4, 5 };
    int n = sizeof(q) / sizeof(q[0]);
 
    performQueries(q, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
static int MAX = 1000000;
 
static int MOD = 10000007;
 
// Declare result array globally
static int []result = new int [MAX + 1];
static int []fact = new int [MAX + 1];
 
// Function to precompute the product
// of factorials upto MAX
static void preCompute()
{
 
    // Initialize base condition if n = 0
    // then factorial of 0 is equal to 1
    // and answer for n = 0 is 1
    fact[0] = 1;
    result[0] = 1;
 
    // Iterate loop from 1 to MAX
    for (int i = 1; i <= MAX; i++)
    {
 
        // factorial(i) = factorial(i - 1) * i
        fact[i] = ((fact[i - 1] % MOD) * i) % MOD;
 
        // Result for current n is equal to result[i-1]
        // multiplied by the factorial of i
        result[i] = ((result[i - 1] % MOD) *
                   (fact[i] % MOD)) % MOD;
    }
}
 
// Function to perform the queries
static void performQueries(int q[], int n)
{
 
    // Precomputing the result till MAX
    preCompute();
 
    // Perform queries
    for (int i = 0; i < n; i++)
        System.out.println (result[q[i]]);
}
 
// Driver code
public static void main (String[] args)
{
    int q[] = { 4, 5 };
    int n = q.length;
     
    performQueries(q, n);
}
}
 
// This code is contributed by tushil.

Python3

# Python3 implementation of the approach
 
MAX = 1000000
MOD = 10**9 + 7
 
# Declare result array globally
result = [0 for i in range(MAX + 1)]
fact = [0 for i in range(MAX + 1)]
 
# Function to precompute the product
# of factorials upto MAX
def preCompute():
 
    # Initialize base condition if n = 0
    # then factorial of 0 is equal to 1
    # and answer for n = 0 is 1
    fact[0] = 1
    result[0] = 1
 
    # Iterate loop from 1 to MAX
    for i in range(1, MAX + 1):
 
        # factorial(i) = factorial(i - 1) * i
        fact[i] = ((fact[i - 1] % MOD) * i) % MOD
 
        # Result for current n is 
        # equal to result[i-1]
        # multiplied by the factorial of i
        result[i] = ((result[i - 1] % MOD) *
                     (fact[i] % MOD)) % MOD
 
# Function to perform the queries
def performQueries(q, n):
 
    # Precomputing the result tiMAX
    preCompute()
 
    # Perform queries
    for i in range(n):
        print(result[q[i]])
 
# Driver code
q = [4, 5]
n = len(q)
 
performQueries(q, n)
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
static int MAX = 1000000;
 
static int MOD = 10000007;
 
// Declare result array globally
static int []result = new int [MAX + 1];
static int []fact = new int [MAX + 1];
 
// Function to precompute the product
// of factorials upto MAX
static void preCompute()
{
 
    // Initialize base condition if n = 0
    // then factorial of 0 is equal to 1
    // and answer for n = 0 is 1
    fact[0] = 1;
    result[0] = 1;
 
    // Iterate loop from 1 to MAX
    for (int i = 1; i <= MAX; i++)
    {
 
        // factorial(i) = factorial(i - 1) * i
        fact[i] = ((fact[i - 1] % MOD) * i) % MOD;
 
        // Result for current n is equal to result[i-1]
        // multiplied by the factorial of i
        result[i] = ((result[i - 1] % MOD) *
                     (fact[i] % MOD)) % MOD;
    }
}
 
// Function to perform the queries
static void performQueries(int []q, int n)
{
 
    // Precomputing the result till MAX
    preCompute();
 
    // Perform queries
    for (int i = 0; i < n; i++)
        Console.WriteLine(result[q[i]]);
}
 
// Driver code
public static void Main (String[] args)
{
    int []q = { 4, 5 };
    int n = q.Length;
     
    performQueries(q, n);
}
}
     
// This code is contributed by 29AjayKumar

Javascript

<script>
    // Javascript implementation of the approach
     
    let MAX = 1000000;
   
    let MOD = 10000007;
 
    // Declare result array globally
    let result = new Array(MAX + 1);
    result.fill(0);
    let fact = new Array(MAX + 1);
    fact.fill(0);
 
    // Function to precompute the product
    // of factorials upto MAX
    function preCompute()
    {
 
        // Initialize base condition if n = 0
        // then factorial of 0 is equal to 1
        // and answer for n = 0 is 1
        fact[0] = 1;
        result[0] = 1;
 
        // Iterate loop from 1 to MAX
        for (let i = 1; i <= MAX; i++)
        {
 
            // factorial(i) = factorial(i - 1) * i
            fact[i] = ((fact[i - 1] % MOD) * i) % MOD;
 
            // Result for current n is equal to result[i-1]
            // multiplied by the factorial of i
            result[i] = ((result[i - 1] % MOD) *
                         (fact[i] % MOD)) % MOD;
        }
    }
 
    // Function to perform the queries
    function performQueries(q, n)
    {
 
        // Precomputing the result till MAX
        preCompute();
 
        // Perform queries
        for (let i = 0; i < n; i++)
            document.write(result[q[i]] + "</br>");
    }
     
    let q = [ 4, 5 ];
    let n = q.length;
       
    performQueries(q, n);
     
</script>
Producción: 

288
34560

 

Complejidad de tiempo: O (MAX)

Espacio Auxiliar: O(MAX)

Publicación traducida automáticamente

Artículo escrito por UdayBhardwaj 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 *