Запросы nCr% p с временной сложностью O (1)

Опубликовано: 16 Января, 2022

Учитывая Q запросов и P, где P - простое число, в каждом запросе есть два числа N и R, и задача состоит в том, чтобы вычислить nCr mod p.
Ограничения:

 N <= 10 ⁶
R <= 10 ⁶
p - простое число

Примеры:

Input:
Q = 2 p = 1000000007
1st query: N = 15, R = 4
2nd query: N = 20, R = 3
Output:
1st query: 1365
2nd query: 1140
15!/(4!*(15-4)!)%1000000007 = 1365
20!/(20!*(20-3)!)%1000000007 = 1140

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход - вычислить nCr по формулам, применяя модульные операции в любое время. Следовательно, временная сложность будет O (q * n).

Лучше использовать малую теорему Ферма. В соответствии с этим nCr также может быть записано как (n! / (R! * (Nr)!)) Mod, что эквивалентно (n! * Inverse (r!) * Inverse ((nr)!)) Mod p . Таким образом, предварительное вычисление факториала чисел от 1 до n позволит отвечать на запросы за O (log n). Единственное, что нужно сделать, это вычислить обратное значение r! и (nr) !. Следовательно, общая сложность будет q * (log (n)) .

Эффективным подходом будет сведение лучшего подхода к эффективному путем предварительного вычисления инверсии факториалов. Предварительно вычислите инверсию факториала за время O (n), а затем на запросы можно будет ответить за время O (1). Число, обратное натуральному числу от 1 до N, может быть вычислено за время O (n) с помощью модульного мультипликативного обратного преобразования. Используя рекурсивное определение факториала, можно записать следующее:

 п! = п * (п-1)!
принимая обратное с обеих сторон 
инверсия (п!) = инверсия (п) * инверсия ((п-1)!)

Поскольку максимальное значение N равно 10 ⁶ , подойдет предварительное вычисление значений до 10 ⁶ .

Below is the implementation of the above approach:

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>

Output:

1365
1140

Сложность времени: O (10 ⁶ ) для предварительного вычисления и O (1) для каждого запроса.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Запросы nCr% p с временной сложностью O (1)

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ