Producto de primeros N factoriales

Dado un número N. Encuentra el producto de los primeros N factoriales módulo 1000000007. 

Restricciones: 1 ≤ N ≤ 1e6  

Ejemplos:  

Input : 3
Output : 12
Explanation: 1! * 2! * 3! = 12 mod (1e9 + 7) = 12

Input : 5
Output : 34560

Requisitos previos: enfoque de multiplicación modular : la idea básica detrás de la solución de este problema es considerar el problema del desbordamiento durante la multiplicación de números tan grandes, es decir, factoriales. Por lo tanto, debe abordarse multiplicando recursivamente para superar la dificultad del desbordamiento. Además, tenemos que tomar el módulo en cada paso mientras calculamos los factoriales de forma iterativa y la multiplicación modular. 

 

facti = facti-1 * i
where facti is the factorial of ith number

prodi = prodi-1 * facti
where prodi is the product of first i factorials

Para encontrar el producto de dos números grandes en módulo, usamos el mismo enfoque que la exponenciación en módulo … En la función de multiplicación, usamos + en lugar de *.
A continuación se muestra la implementación del enfoque anterior. 

C++

// CPP Program to find the
// product of first N factorials
#include <bits/stdc++.h>
 
using namespace std;
 
// To compute (a * b) % MOD
long long int mulmod(long long int a, long long int b,
                                    long long int mod)
{
    long long int res = 0; // Initialize result
    a = a % mod;
    while (b > 0) {
 
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;
 
        // Multiply 'a' with 2
        a = (a * 2) % mod;
 
        // Divide b by 2
        b /= 2;
    }
 
    // Return result
    return res % mod;
}
 
// This function computes factorials and
// product by using above function i.e.
// modular multiplication
long long int findProduct(long long int N)
{
    // Initialize product and fact with 1
    long long int product = 1, fact = 1;
    long long int MOD = 1e9 + 7;
    for (int i = 1; i <= N; i++) {
 
        // ith factorial
        fact = mulmod(fact, i, MOD);
 
        // product of first i factorials
        product = mulmod(product, fact, MOD);
 
        // If at any iteration, product becomes
        // divisible by MOD, simply return 0;
        if (product == 0)
            return 0;
    }
    return product;
}
 
// Driver Code to Test above functions
int main()
{
    long long int N = 3;
    cout << findProduct(N) << endl;
 
    N = 5;
    cout << findProduct(N) << endl;
 
    return 0;
}

Java

// Java Program to find the
// product of first N factorials
 
class GFG{
// To compute (a * b) % MOD
static double mulmod(long a, long b,
                                    long mod)
{
    long res = 0; // Initialize result
    a = a % mod;
    while (b > 0) {
 
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;
 
        // Multiply 'a' with 2
        a = (a * 2) % mod;
 
        // Divide b by 2
        b /= 2;
    }
 
    // Return result
    return res % mod;
}
 
// This function computes factorials and
// product by using above function i.e.
// modular multiplication
static long findProduct(long N)
{
    // Initialize product and fact with 1
    long product = 1, fact = 1;
    long MOD = (long)(1e9 + 7);
    for (int i = 1; i <= N; i++) {
 
        // ith factorial
        fact = (long)mulmod(fact, i, MOD);
 
        // product of first i factorials
        product = (long)mulmod(product, fact, MOD);
 
        // If at any iteration, product becomes
        // divisible by MOD, simply return 0;
        if (product == 0)
            return 0;
    }
    return product;
}
 
// Driver Code to Test above functions
public static void main(String[] args)
{
    long N = 3;
    System.out.println(findProduct(N));
 
    N = 5;
    System.out.println(findProduct(N));
 
}
}
// this Code is contributed by mits

Python3

# Python Program to find the
# product of first N factorials
 
# To compute (a * b) % MOD
def mulmod(a, b, mod):
    res = 0 # Initialize result
    a = a % mod
    while (b > 0):
 
        # If b is odd, add 'a' to result
        if (b % 2 == 1):
            res = (res + a) % mod
 
        # Multiply 'a' with 2
        a = (a * 2) % mod
 
        # Divide b by 2
        b //= 2
 
    # Return result
    return res % mod
 
# This function computes factorials and
# product by using above function i.e.
# modular multiplication
def findProduct(N):
    # Initialize product and fact with 1
    product = 1; fact = 1
    MOD = 1e9 + 7
    for i in range(1, N+1):
 
        # ith factorial
        fact = mulmod(fact, i, MOD)
 
        # product of first i factorials
        product = mulmod(product, fact, MOD)
 
        # If at any iteration, product becomes
        # divisible by MOD, simply return 0
        if not product:
            return 0
    return int(product)
 
# Driver Code to Test above functions
N = 3
print(findProduct(N))
N = 5
print(findProduct(N))
 
# This code is contributed by Ansu Kumari

C#

// C#  Program to find the
// product of first N factorials
 
using System;
 
public class GFG{
    // To compute (a * b) % MOD
static double mulmod(long a, long b,
                                    long mod)
{
    long res = 0; // Initialize result
    a = a % mod;
    while (b > 0) {
 
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;
 
        // Multiply 'a' with 2
        a = (a * 2) % mod;
 
        // Divide b by 2
        b /= 2;
    }
 
    // Return result
    return res % mod;
}
 
// This function computes factorials and
// product by using above function i.e.
// modular multiplication
static long findProduct(long N)
{
    // Initialize product and fact with 1
    long product = 1, fact = 1;
    long MOD = (long)(1e9 + 7);
    for (int i = 1; i <= N; i++) {
 
        // ith factorial
        fact = (long)mulmod(fact, i, MOD);
 
        // product of first i factorials
        product = (long)mulmod(product, fact, MOD);
 
        // If at any iteration, product becomes
        // divisible by MOD, simply return 0;
        if (product == 0)
            return 0;
    }
    return product;
}
 
// Driver Code to Test above functions
    static public void Main (){
        long N = 3;
        Console.WriteLine(findProduct(N));
        N = 5;
        Console.WriteLine(findProduct(N));
 
}
}
//This Code is contributed by ajit.

PHP

<?php
// PHP Program to find the
// product of first N factorials
 
// To compute (a * b) % MOD
function mulmod($a, $b, $mod)
{
    $res = 0; // Initialize result
    $a = $a % $mod;
    while ($b > 0)
    {
 
        // If b is odd, add 'a' to result
        if ($b % 2 == 1)
            $res = ($res + $a) % $mod;
 
        // Multiply 'a' with 2
        $a = ($a * 2) % $mod;
 
        // Divide b by 2
        $b /= 2;
    }
 
    // Return result
    return $res % $mod;
}
 
// This function computes factorials and
// product by using above function i.e.
// modular multiplication
function findProduct($N)
{
    // Initialize product and fact with 1
    $product = 1;
    $fact = 1;
    $MOD = 1000000000;
    for ($i = 1; $i <= $N; $i++)
    {
 
        // ith factorial
        $fact = mulmod($fact, $i, $MOD);
 
        // product of first i factorials
        $product = mulmod($product, $fact, $MOD);
 
        // If at any iteration, product becomes
        // divisible by MOD, simply return 0;
        if ($product == 0)
            return 0;
    }
    return $product;
}
 
// Driver Code
$N = 3;
echo findProduct($N),"\n";
 
$N = 5;
echo findProduct($N),"\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
    // Javascript Program to find the
    // product of first N factorials
     
    // To compute (a * b) % MOD
    function mulmod(a, b, mod)
    {
        let res = 0; // Initialize result
        a = a % mod;
        while (b > 0) {
 
            // If b is odd, add 'a' to result
            if (b % 2 == 1)
                res = (res + a) % mod;
 
            // Multiply 'a' with 2
            a = (a * 2) % mod;
 
            // Divide b by 2
            b = parseInt(b / 2, 10);
        }
 
        // Return result
        return res % mod;
    }
 
    // This function computes factorials and
    // product by using above function i.e.
    // modular multiplication
    function findProduct(N)
    {
        // Initialize product and fact with 1
        let product = 1, fact = 1;
        let MOD = (1e9 + 7);
        for (let i = 1; i <= N; i++) {
 
            // ith factorial
            fact = mulmod(fact, i, MOD);
 
            // product of first i factorials
            product = mulmod(product, fact, MOD);
 
            // If at any iteration, product becomes
            // divisible by MOD, simply return 0;
            if (product == 0)
                return 0;
        }
        return product;
    }
     
    let N = 3;
    document.write(findProduct(N) + "</br>");
   
    N = 5;
    document.write(findProduct(N));
 
</script>
Producción: 

12
34560

 

Complejidad temporal: O(N * logN), donde O(log N) es la complejidad temporal de la multiplicación modular.
 

Publicación traducida automáticamente

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