Consultas de nCr%p en complejidad de tiempo O(1)

Posted on by Rudeus Greyrat

Dadas las consultas Q y P donde P es un número primo, cada consulta tiene dos números N y R y la tarea es calcular nCr mod p. 
Restricciones: 

N <= 106
R <= 106
p is a prime number

Ejemplos:

Entrada: 
Q = 2 p = 1000000007 
1ra consulta: N = 15, R = 4 
2da consulta: N = 20, R = 3 
Salida: 
1ra consulta: 1365 
2da consulta: 1140 
15!/(4!*(15-4) !)%1000000007 = 1365 
20!/(20!*(20-3)!)%1000000007 = 1140

Un enfoque ingenuo es calcular nCr usando fórmulas aplicando operaciones modulares en cualquier momento. Por lo tanto, la complejidad del tiempo será O(q*n).

Un mejor enfoque es usar el pequeño teorema de Fermat . De acuerdo con esto, nCr también se puede escribir como (n!/(r!*(nr)!) ) mod que es equivalente a (n!*inverse(r!)*inverse((nr)!) ) mod p . Por lo tanto, el precálculo factorial de números del 1 al n permitirá que las consultas se respondan en O (log n). ¡El único cálculo que debe hacerse es calcular el inverso de r! y (nr)!. Por lo tanto, la complejidad general será q*( log(n)) .

Un enfoque eficiente será reducir el mejor enfoque a uno eficiente calculando previamente el inverso de los factoriales. Calcule previamente el inverso del factorial en tiempo O(n) y luego las consultas se pueden responder en tiempo O(1). El inverso de 1 a N número natural se puede calcular en tiempo O(n) usando el inverso multiplicativo modular . Usando la definición recursiva de factorial, se puede escribir lo siguiente:

n! = n * (n-1) !
taking inverse on both side 
inverse( n! ) = inverse( n ) * inverse( (n-1)! )

Dado que el valor máximo de N es 10 6 , precalcular valores hasta 10 6 servirá.

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

C++

// C++ program to answer queries
// of nCr in O(1) time.
#include <bits/stdc++.h>
#define ll long long
const int N = 1000001;
using namespace std;
 
// array to store inverse of 1 to N
ll factorialNumInverse[N + 1];
 
// array to precompute inverse of 1! to N!
ll naturalNumInverse[N + 1];
 
// array to store factorial of first N numbers
ll fact[N + 1];
 
// Function to precompute inverse of numbers
void InverseofNumber(ll p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
    for (int i = 2; i <= N; i++)
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
// Function to precompute inverse of factorials
void InverseofFactorial(ll p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;
 
    // precompute inverse of natural numbers
    for (int i = 2; i <= N; i++)
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
 
// Function to calculate factorial of 1 to N
void factorial(ll p)
{
    fact[0] = 1;
 
    // precompute factorials
    for (int i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
}
 
// Function to return nCr % p in O(1) time
ll Binomial(ll N, ll R, ll p)
{
    // n C r = n!*inverse(r!)*inverse((n-r)!)
    ll ans = ((fact[N] * factorialNumInverse[R])
              % p * factorialNumInverse[N - R])
             % p;
    return ans;
}
 
// Driver Code
int main()
{
    // Calling functions to precompute the
    // required arrays which will be required
    // to answer every query in O(1)
    ll p = 1000000007;
    InverseofNumber(p);
    InverseofFactorial(p);
    factorial(p);
 
    // 1st query
    ll N = 15;
    ll R = 4;
    cout << Binomial(N, R, p) << endl;
 
    // 2nd query
    N = 20;
    R = 3;
    cout << Binomial(N, R, p) << endl;
 
    return 0;
}

Java

// Java program to answer queries
// of nCr in O(1) time
import java.io.*;
 
class GFG{
     
static int N = 1000001; 
 
// Array to store inverse of 1 to N
static long[] factorialNumInverse = new long[N + 1];
 
// Array to precompute inverse of 1! to N!
static long[] naturalNumInverse = new long[N + 1];
 
// Array to store factorial of first N numbers
static long[] fact = new long[N + 1];
 
// Function to precompute inverse of numbers
public static void InverseofNumber(int p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
     
    for(int i = 2; i <= N; i++)
        naturalNumInverse[i] = naturalNumInverse[p % i] *
                                 (long)(p - p / i) % p;
}
 
// Function to precompute inverse of factorials
public static void InverseofFactorial(int p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;
 
    // Precompute inverse of natural numbers
    for(int i = 2; i <= N; i++)
        factorialNumInverse[i] = (naturalNumInverse[i] *
                           factorialNumInverse[i - 1]) % p;
}
 
// Function to calculate factorial of 1 to N
public static void factorial(int p)
{
    fact[0] = 1;
 
    // Precompute factorials
    for(int i = 1; i <= N; i++)
    {
        fact[i] = (fact[i - 1] * (long)i) % p;
    }
}
 
// Function to return nCr % p in O(1) time
public static long Binomial(int N, int R, int p)
{
     
    // n C r = n!*inverse(r!)*inverse((n-r)!)
    long ans = ((fact[N] * factorialNumInverse[R]) %
                       p * factorialNumInverse[N - R]) % p;
     
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
     
    // Calling functions to precompute the
    // required arrays which will be required
    // to answer every query in O(1)
    int p = 1000000007;
    InverseofNumber(p);
    InverseofFactorial(p);
    factorial(p);
     
    // 1st query
    int n = 15;
    int R = 4;
    System.out.println(Binomial(n, R, p));
     
    // 2nd query
    n = 20;
    R = 3;
    System.out.println(Binomial(n, R, p));
}
}
 
// This code is contributed by RohitOberoi

Python3

# Python3 program to answer queries
# of nCr in O(1) time.
N = 1000001
 
# array to store inverse of 1 to N
factorialNumInverse = [None] * (N + 1)
 
# array to precompute inverse of 1! to N!
naturalNumInverse = [None] * (N + 1)
 
# array to store factorial of
# first N numbers
fact = [None] * (N + 1)
 
# Function to precompute inverse of numbers
def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = (naturalNumInverse[p % i] *
                                   (p - int(p / i)) % p)
 
# Function to precompute inverse
# of factorials
def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1
 
    # precompute inverse of natural numbers
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = (naturalNumInverse[i] *
                                  factorialNumInverse[i - 1]) % p
 
# Function to calculate factorial of 1 to N
def factorial(p):
    fact[0] = 1
 
    # precompute factorials
    for i in range(1, N + 1):
        fact[i] = (fact[i - 1] * i) % p
 
# Function to return nCr % p in O(1) time
def Binomial(N, R, p):
     
    # n C r = n!*inverse(r!)*inverse((n-r)!)
    ans = ((fact[N] * factorialNumInverse[R])% p *
                      factorialNumInverse[N - R])% p
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Calling functions to precompute the
    # required arrays which will be required
    # to answer every query in O(1)
    p = 1000000007
    InverseofNumber(p)
    InverseofFactorial(p)
    factorial(p)
 
    # 1st query
    N = 15
    R = 4
    print(Binomial(N, R, p))
 
    # 2nd query
    N = 20
    R = 3
    print(Binomial(N, R, p))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to answer queries 
// of nCr in O(1) time
using System;
 
class GFG{
     
static int N = 1000001;  
 
// Array to store inverse of 1 to N 
static long[] factorialNumInverse = new long[N + 1]; 
   
// Array to precompute inverse of 1! to N! 
static long[] naturalNumInverse = new long[N + 1];
   
// Array to store factorial of first N numbers 
static long[] fact = new long[N + 1]; 
   
// Function to precompute inverse of numbers 
static void InverseofNumber(int p) 
{ 
    naturalNumInverse[0] = naturalNumInverse[1] = 1; 
       
    for(int i = 2; i <= N; i++) 
        naturalNumInverse[i] = naturalNumInverse[p % i] *
                                 (long)(p - p / i) % p; 
} 
   
// Function to precompute inverse of factorials 
static void InverseofFactorial(int p) 
{ 
    factorialNumInverse[0] = factorialNumInverse[1] = 1; 
   
    // Precompute inverse of natural numbers 
    for(int i = 2; i <= N; i++) 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                            factorialNumInverse[i - 1]) % p; 
} 
   
// Function to calculate factorial of 1 to N 
static void factorial(int p) 
{ 
    fact[0] = 1; 
   
    // Precompute factorials 
    for(int i = 1; i <= N; i++)
    { 
        fact[i] = (fact[i - 1] * (long)i) % p; 
    } 
} 
   
// Function to return nCr % p in O(1) time 
static long Binomial(int N, int R, int p) 
{ 
       
    // n C r = n!*inverse(r!)*inverse((n-r)!) 
    long ans = ((fact[N] * factorialNumInverse[R]) % 
                       p * factorialNumInverse[N - R]) % p; 
       
    return ans; 
}
 
// Driver code
static void Main()
{
     
    // Calling functions to precompute the 
    // required arrays which will be required 
    // to answer every query in O(1) 
    int p = 1000000007; 
    InverseofNumber(p); 
    InverseofFactorial(p); 
    factorial(p); 
       
    // 1st query 
    int n = 15; 
    int R = 4; 
    Console.WriteLine(Binomial(n, R, p));
       
    // 2nd query 
    n = 20; 
    R = 3; 
    Console.WriteLine(Binomial(n, R, p));
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript program to answer queries
// of nCr in O(1) time.
var N = 1000001;
 
// array to store inverse of 1 to N
factorialNumInverse = Array(N+1).fill(0);
 
// array to precompute inverse of 1! to N!
naturalNumInverse = Array(N+1).fill(0);
 
// array to store factorial of first N numbers
fact = Array(N+1).fill(0);
 
// Function to precompute inverse of numbers
function InverseofNumber(p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
    for (var i = 2; i <= N; i++)
        naturalNumInverse[i] = (naturalNumInverse[p % i] * (p - parseInt(p / i))) % p;
}
 
// Function to precompute inverse of factorials
function InverseofFactorial(p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;
 
    // precompute inverse of natural numbers
    for (var i = 2; i <= N; i++)
        factorialNumInverse[i] = ((naturalNumInverse[i] * factorialNumInverse[i - 1])) % p;
}
 
// Function to calculate factorial of 1 to N
function factorial(p)
{
    fact[0] = 1;
 
    // precompute factorials
    for (var i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
}
 
// Function to return nCr % p in O(1) time
function Binomial(N, R, p)
{
 
    // n C r = n!*inverse(r!)*inverse((n-r)!)
    var ans = ((((fact[N] * factorialNumInverse[R])% p) * factorialNumInverse[N - R]))% p;
    return ans;
}
 
// Driver Code
 
// Calling functions to precompute the
// required arrays which will be required
// to answer every query in O(1)
p = 100000007;
InverseofNumber(p);
InverseofFactorial(p);
factorial(p);
 
// 1st query
N = 15;
R = 4;
document.write(Binomial(N, R, p)+"<br>")
 
// 2nd query
N = 20;
R = 3;
document.write(Binomial(N, R, p));
 
// This code is contributed by noob2000.
</script>
Producción: 

1365
1140

Complejidad de tiempo: O(N) para precálculo y O(1) para cada consulta.
Espacio Auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por jitendra yadav 2 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 *