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>
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