Dados tres números n, r y p, calcule el valor de n C r mod p.
Ejemplos:
Input: n = 10, r = 2, p = 13 Output: 6 Explanation: 10C2 is 45 and 45 % 13 is 6. Input: n = 1000, r = 900, p = 13 Output: 8
Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto.
Calcule n C r % p | Conjunto 1 (Introducción y Solución de Programación Dinámica)
Hemos introducido el problema de desbordamiento y discutido la solución basada en Programación Dinámica en el conjunto 1 anterior. La complejidad de tiempo de la solución basada en DP es O(n*r) y requiere espacio O(n). El tiempo necesario y el espacio adicional se vuelven muy altos para valores grandes de n, especialmente valores cercanos a 10 9 .
En esta publicación, se analiza la solución basada en el teorema de Lucas. La complejidad temporal de esta solución es O(p 2 * Log p n) y solo requiere espacio O(p).
Teorema de Lucas:
Para números enteros no negativos n y r y un primo p, se cumple la siguiente relación de congruencia: 
donde 
y 
Uso del teorema de Lucas para n C r % p:
El teorema de Lucas básicamente sugiere que el valor de n C r se puede calcular multiplicando los resultados de ni C ri donde n i y r i son dígitos individuales en la misma posición en representaciones en base p de n y r respectivamente. .
La idea es calcular uno por uno n i C ri para dígitos individuales n i y r ien base p. Podemos calcular estos valores en la solución basada en DP discutida en la publicación anterior . Dado que estos dígitos están en base p, nunca necesitaríamos más de O(p). La complejidad espacial y temporal de estos cálculos individuales estaría limitada por O(p 2 ).
A continuación se muestra la implementación de la idea anterior.
C++
// A Lucas Theorem based solution to compute nCr % p
#include<bits/stdc++.h>
using namespace std;
// Returns nCr % p. In this Lucas Theorem based program,
// this function is only called for n < p and r < p.
int nCrModpDP(int n, int r, int p)
{
// The array C is going to store last row of
// pascal triangle at the end. And last entry
// of last row is nCr
int C[r+1];
memset(C, 0, sizeof(C));
C[0] = 1; // Top row of Pascal Triangle
// One by constructs remaining rows of Pascal
// Triangle from top to bottom
for (int i = 1; i <= n; i++)
{
// Fill entries of current row using previous
// row values
for (int j = min(i, r); j > 0; j--)
// nCj = (n-1)Cj + (n-1)C(j-1);
C[j] = (C[j] + C[j-1])%p;
}
return C[r];
}
// Lucas Theorem based function that returns nCr % p
// This function works like decimal to binary conversion
// recursive function. First we compute last digits of
// n and r in base p, then recur for remaining digits
int nCrModpLucas(int n, int r, int p)
{
// Base case
if (r==0)
return 1;
// Compute last digits of n and r in base p
int ni = n%p, ri = r%p;
// Compute result for last digits computed above, and
// for remaining digits. Multiply the two results and
// compute the result of multiplication in modulo p.
return (nCrModpLucas(n/p, r/p, p) * // Last digits of n and r
nCrModpDP(ni, ri, p)) % p; // Remaining digits
}
// Driver program
int main()
{
int n = 1000, r = 900, p = 13;
cout << "Value of nCr % p is " << nCrModpLucas(n, r, p);
return 0;
}
Java
// A Lucas Theorem based solution to compute nCr % p
class GFG{
// Returns nCr % p. In this Lucas Theorem based program,
// this function is only called for n < p and r < p.
static int nCrModpDP(int n, int r, int p)
{
// The array C is going to store last row of
// pascal triangle at the end. And last entry
// of last row is nCr
int[] C=new int[r+1];
C[0] = 1; // Top row of Pascal Triangle
// One by constructs remaining rows of Pascal
// Triangle from top to bottom
for (int i = 1; i <= n; i++)
{
// Fill entries of current row using previous
// row values
for (int j = Math.min(i, r); j > 0; j--)
// nCj = (n-1)Cj + (n-1)C(j-1);
C[j] = (C[j] + C[j-1])%p;
}
return C[r];
}
// Lucas Theorem based function that returns nCr % p
// This function works like decimal to binary conversion
// recursive function. First we compute last digits of
// n and r in base p, then recur for remaining digits
static int nCrModpLucas(int n, int r, int p)
{
// Base case
if (r==0)
return 1;
// Compute last digits of n and r in base p
int ni = n%p;
int ri = r%p;
// Compute result for last digits computed above, and
// for remaining digits. Multiply the two results and
// compute the result of multiplication in modulo p.
return (nCrModpLucas(n/p, r/p, p) * // Last digits of n and r
nCrModpDP(ni, ri, p)) % p; // Remaining digits
}
// Driver program
public static void main(String[] args)
{
int n = 1000, r = 900, p = 13;
System.out.println("Value of nCr % p is "+nCrModpLucas(n, r, p));
}
}
// This code is contributed by mits
Python3
# A Lucas Theorem based solution
# to compute nCr % p
# Returns nCr % p. In this Lucas
# Theorem based program, this
# function is only called for
# n < p and r < p.
def nCrModpDP(n, r, p):
# The array C is going to store
# last row of pascal triangle
# at the end. And last entry
# of last row is nCr
C = [0] * (n + 1);
# Top row of Pascal Triangle
C[0] = 1;
# One by constructs remaining
# rows of Pascal Triangle from
# top to bottom
for i in range(1, (n + 1)):
# Fill entries of current
# row using previous row
# values
j = min(i, r);
while(j > 0):
C[j] = (C[j] + C[j - 1]) % p;
j -= 1;
return C[r];
# Lucas Theorem based function that
# returns nCr % p. This function
# works like decimal to binary
# conversion recursive function.
# First we compute last digits of
# n and r in base p, then recur
# for remaining digits
def nCrModpLucas(n, r, p):
# Base case
if (r == 0):
return 1;
# Compute last digits of n
# and r in base p
ni = int(n % p);
ri = int(r % p);
# Compute result for last digits
# computed above, and for remaining
# digits. Multiply the two results
# and compute the result of
# multiplication in modulo p.
# Last digits of n and r
return (nCrModpLucas(int(n / p), int(r / p), p) *
nCrModpDP(ni, ri, p)) % p; # Remaining digits
# Driver Code
n = 1000;
r = 900;
p = 13;
print("Value of nCr % p is",
nCrModpLucas(n, r, p));
# This code is contributed by mits
C#
// A Lucas Theorem based solution
// to compute nCr % p
using System;
class GFG
{
// Returns nCr % p. In this Lucas
// Theorem based program, this
// function is only called for
// n < p and r < p.
static int nCrModpDP(int n, int r, int p)
{
// The array C is going to store
// last row of pascal triangle
// at the end. And last entry
// of last row is nCr
int[] C = new int[r + 1];
C[0] = 1; // Top row of Pascal Triangle
// One by constructs remaining
// rows of Pascal Triangle
// from top to bottom
for (int i = 1; i <= n; i++)
{
// Fill entries of current row
// using previous row values
for (int j = Math.Min(i, r); j > 0; j--)
// nCj = (n-1)Cj + (n-1)C(j-1);
C[j] = (C[j] + C[j - 1]) % p;
}
return C[r];
}
// Lucas Theorem based function that
// returns nCr % p. This function works
// like decimal to binary conversion
// recursive function. First we compute
// last digits of n and r in base p,
// then recur for remaining digits
static int nCrModpLucas(int n, int r, int p)
{
// Base case
if (r == 0)
return 1;
// Compute last digits of n
// and r in base p
int ni = n % p;
int ri = r % p;
// Compute result for last digits
// computed above, and for remaining
// digits. Multiply the two results
// and compute the result of
// multiplication in modulo p.
return (nCrModpLucas(n / p, r / p, p) * // Last digits of n and r
nCrModpDP(ni, ri, p)) % p; // Remaining digits
}
// Driver Code
public static void Main()
{
int n = 1000, r = 900, p = 13;
Console.Write("Value of nCr % p is " +
nCrModpLucas(n, r, p));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// A Lucas Theorem based
// solution to compute
// nCr % p
// Returns nCr % p. In this
// Lucas Theorem based program,
// this function is only called
// for n < p and r < p.
function nCrModpDP($n, $r, $p)
{
// The array C is going to
// store last row of pascal
// triangle at the end. And
// last entry of last row is nCr
$C = array_fill(0, $n + 1,
false);
// Top row of
// Pascal Triangle
$C[0] = 1;
// One by constructs remaining
// rows of Pascal Triangle from
// top to bottom
for ($i = 1; $i <= $n; $i++)
{
// Fill entries of current
// row using previous row
// values
for ($j = min($i, $r);
$j > 0; $j--)
$C[$j] = ($C[$j] +
$C[$j - 1]) % $p;
}
return $C[$r];
}
// Lucas Theorem based function
// that returns nCr % p. This
// function works like decimal
// to binary conversion recursive
// function. First we compute last
// digits of n and r in base p,
// then recur for remaining digits
function nCrModpLucas($n, $r, $p)
{
// Base case
if ($r == 0)
return 1;
// Compute last digits
// of n and r in base p
$ni = $n % $p;
$ri = $r % $p;
// Compute result for last
// digits computed above,
// and for remaining digits.
// Multiply the two results
// and compute the result of
// multiplication in modulo p.
return (nCrModpLucas($n / $p,
$r / $p, $p) * // Last digits of n and r
nCrModpDP($ni, $ri, $p)) % $p; // Remaining digits
}
// Driver Code
$n = 1000; $r = 900; $p = 13;
echo "Value of nCr % p is " ,
nCrModpLucas($n, $r, $p);
// This code is contributed by ajit
?>
Javascript
<script>
// A Lucas Theorem based solution to compute nCr % p
// Returns nCr % p. In this Lucas Theorem based program,
// this function is only called for n < p and r < p.
function nCrModpDP(n, r, p)
{
// The array C is going to store last row of
// pascal triangle at the end. And last entry
// of last row is nCr
C = Array(r+1).fill(0);
C[0] = 1; // Top row of Pascal Triangle
// One by constructs remaining rows of Pascal
// Triangle from top to bottom
for (var i = 1; i <= n; i++)
{
// Fill entries of current row using previous
// row values
for (var j = Math.min(i, r); j > 0; j--)
// nCj = (n-1)Cj + (n-1)C(j-1);
C[j] = (C[j] + C[j-1])%p;
}
return C[r];
}
// Lucas Theorem based function that returns nCr % p
// This function works like decimal to binary conversion
// recursive function. First we compute last digits of
// n and r in base p, then recur for remaining digits
function nCrModpLucas(n, r, p)
{
// Base case
if (r==0)
return 1;
// Compute last digits of n and r in base p
var ni = n%p, ri = r%p;
// Compute result for last digits computed above, and
// for remaining digits. Multiply the two results and
// compute the result of multiplication in modulo p.
return (nCrModpLucas(parseInt(n/p), parseInt(r/p), p) * // Last digits of n and r
nCrModpDP(ni, ri, p)) % p; // Remaining digits
}
// Driver program
var n = 1000, r = 900, p = 13;
document.write("Value of nCr % p is " + nCrModpLucas(n, r, p));
</script>
Producción:
Value of nCr % p is 8
Complejidad de tiempo: La complejidad de tiempo de esta solución es O(p 2 * Log p n). Hay O(Log p n) dígitos en base p representación de n. Cada uno de estos dígitos es menor que p, por lo tanto, los cálculos para dígitos individuales toman O(p 2 ). Tenga en cuenta que estos cálculos se realizan mediante el método DP, que requiere un tiempo O(n*r).
Implementación alternativa con tiempo O(p 2 + Log p n) y espacio O(p 2 ):
la idea es calcular previamente el triángulo de Pascal para el tamaño pxp y almacenarlo en una array 2D. Todos los valores necesarios tomarían ahora O(1) tiempo. Por lo tanto, la complejidad global del tiempo se convierte en O(p 2 + Log pnorte).
Este artículo es una contribución de Ruchir Garg . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA