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