Calcule nCr % p | Set 1 (Introducción y Solución de Programación Dinámica)

Dados tres números n, r y p, calcule el valor de ⁿ C _r mod p. 
Ejemplo: 

Input:  n = 10, r = 2, p = 13
Output: 6
Explanation: 10C2 is 45 and 45 % 13 is 6.

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

MÉTODO 1: (Usando Programación Dinámica)

Una solución simple es calcular primero ⁿ C _r , luego calcular ⁿ C _r % p. Esta solución funciona bien cuando el valor de ⁿ C _r es pequeño. 
¿Qué pasa si el valor de ⁿ C _r es grande?  
El valor de ⁿ C _r %p generalmente se necesita para valores grandes de n cuando ⁿ C _r no cabe en una variable y provoca un desbordamiento. Calculando ⁿ C _ry luego usar un operador modular no es una buena idea ya que habrá un desbordamiento incluso para valores ligeramente mayores de n y r. Por ejemplo, los métodos discutidos aquí y aquí causan un desbordamiento para n = 50 y r = 40.
La idea es calcular ⁿ C _r usando la siguiente fórmula  

   C(n, r) = C(n-1, r-1) + C(n-1, r)
   C(n, 0) = C(n, n) = 1

Funcionamiento de la fórmula anterior y el Triángulo de Pascal: 
Veamos cómo funciona la fórmula anterior para C(4, 3)
1==========>> n = 0, C(0, 0) = 1 
1–1 ========>> n = 1, C(1, 0) = 1, C(1, 1) = 1 
1–2–1======>> n = 2, C( 2, 0) = 1, C(2, 1) = 2, C(2, 2) = 1 
1–3–3–1====>> n = 3, C(3, 0) = 1, C(3, 1) = 3, C(3, 2) = 3, C(3, 3)=1 
1–4–6–4–1==>> n = 4, C(4, 0) = 1, C(4, 1) = 4, C(4, 2) = 6, C(4, 3)=4, C(4, 4)=1 
Así que aquí cada ciclo en i, construye la i-ésima fila de triángulo pascal, usando (i-1) fila
Extensión de la fórmula anterior para la aritmética modular: 
Podemos usar la propiedad distributiva del operador modular para encontrar nCr % p usando la fórmula anterior.

   C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
   C(n, 0) = C(n, n) = 1

La fórmula anterior se puede implementar usando Programación Dinámica usando una array 2D.
La solución de programación dinámica basada en array 2D se puede optimizar aún más mediante la construcción de una fila a la vez. Consulte la versión optimizada para el espacio en la publicación a continuación para obtener más detalles.
Coeficiente binomial usando programación dinámica
A continuación se muestra la implementación basada en la versión optimizada de espacio discutida en la publicación anterior.  

// A Dynamic Programming based solution to compute nCr % p
#include <bits/stdc++.h>
using namespace std;
 
// Returns nCr % p
int nCrModp(int n, int r, int p)
{
    // Optimization for the cases when r is large
    if (r > n - r)
        r = n - r;
 
    // 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];
}
 
// Driver program
int main()
{
    int n = 10, r = 2, p = 13;
    cout << "Value of nCr % p is " << nCrModp(n, r, p);
    return 0;
}

// A Dynamic Programming based
// solution to compute nCr % p
import java.io.*;
import java.util.*;
import java.math.*;
 
class GFG {
 
    // Returns nCr % p
    static int nCrModp(int n, int r, int p)
    {
        if (r > n - r)
            r = n - r;
 
        // 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];
    }
 
    // Driver program
    public static void main(String args[])
    {
        int n = 10, r = 2, p = 13;
        System.out.println("Value of nCr % p is "
                           + nCrModp(n, r, p));
    }
}
 
// This code is contributed by Nikita Tiwari.

# A Dynamic Programming based solution to compute nCr % p
 
# Returns nCr % p
def nCrModp(n, r, p):
 
    # Optimization for the cases when r is large
    # compared to n-r
    if (r > n- r):
        r = n - r 
 
    # 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 for i in range(r + 1)]
 
    C[0] = 1 # Top row of Pascal Triangle
 
    # 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
        for j in range(min(i, r), 0, -1):
 
            # nCj = (n - 1)Cj + (n - 1)C(j - 1)
            C[j] = (C[j] + C[j-1]) % p
 
    return C[r]
 
# Driver Program
n = 10
r = 2
p = 13
print('Value of nCr % p is', nCrModp(n, r, p))
 
# This code is contributed by Soumen Ghosh

// A Dynamic Programming based
// solution to compute nCr % p
using System;
 
class GFG {
 
    // Returns nCr % p
    static int nCrModp(int n, int r, int p)
    {
 
        // Optimization for the cases when r is large
        if (r > n - r)
            r = n - r;
 
        // 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];
 
        for (int i = 0; i < r + 1; i++)
            C[i] = 0;
 
        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];
    }
 
    // Driver program
    public static void Main()
    {
        int n = 10, r = 2, p = 13;
 
        Console.Write("Value of nCr % p is "
                      + nCrModp(n, r, p));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// A Dynamic Programming based
// solution to compute nCr % p
     
// Returns nCr % p
function nCrModp($n, $r, $p)
{
 
// Optimization for the cases when r is large
if ($r > $n - $r)
    $r = $n - $r;
 
// 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();
 
for( $i = 0; $i < $r + 1; $i++)
    $C[$i] = 0;
 
// 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--)
 
        // nCj = (n-1)Cj + (n-1)C(j-1);
        $C[$j] = ($C[$j] +
                  $C[$j - 1]) % $p;
}
 
return $C[$r];
}
 
// Driver Code
$n = 10; $r = 2;$p = 13;
 
echo "Value of nCr % p is ",
         nCrModp($n, $r, $p);
 
// This code is contributed
// by anuj_67.
?>

<script>
// A Dynamic Programming based
// solution to compute nCr % p
 
// Returns nCr % p
function nCrModp(n,r,p)
{
    if (r > n - r)
            r = n - r;
  
        // The array C is going to store last
        // row of pascal triangle at the end.
        // And last entry of last row is nCr
        let C = new Array(r + 1);
         for(let i = 0; i < r + 1; i++)
            C[i] = 0;
        C[0] = 1; // Top row of Pascal Triangle
  
        // One by constructs remaining rows of Pascal
        // Triangle from top to bottom
        for (let i = 1; i <= n; i++) {
  
            // Fill entries of current row using previous
            // row values
            for (let 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];
}
 
// Driver program
let n = 10, r = 2, p = 13;
document.write("Value of nCr % p is "
                   + nCrModp(n, r, p));
 
// This code is contributed by avanitrachhadiya2155
</script>

Value of nCr % p is 6

La complejidad temporal de la solución anterior es O(n*r) y requiere espacio O(r). Hay más y mejores soluciones al problema anterior. 
Calcule nCr % p | Conjunto 2 (Teorema de Lucas)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

MÉTODO 2 (usando Pascal Triangle y Dynamic Pro)

Otro enfoque consiste en utilizar el concepto del Triángulo de Pascal. En lugar de calcular el valor de ⁿ C _r para cada n a partir de n=0 hasta n=n, el enfoque apunta a usar la fila n para el cálculo. El método avanza encontrando una relación general entre ⁿ C _r y ⁿ C _r-1 .

FORMULA: C(n,r)=C(n,r-1)* (n-r+1)/r

Example:

For instance, take n=5 and r=3.

Input:  n = 5, r = 3, p = 1000000007
Output: 6
Explanation: 5C3 is 10 and 10 % 100000007 is 10.


As per the formula,
C(5,3)=5!/(3!)*(2!)
C(5,3)=10

Also,
C(5,2)=5!/(2!)*(3!)
C(5,2)=10


Let's try applying the above formula.

C(n,r)=C(n,r-1)* (n-r+1)/r
C(5,3)=C(5,2)*(5-3+1)/3
C(5,3)=C(5,2)*1
C(5,3)=10*1

El ejemplo anterior muestra que C(n,r) se puede calcular fácilmente calculando C(n,r-1) y multiplicando el resultado por el término (n-r+1)/r. Pero esta multiplicación puede causar un desbordamiento de enteros para valores grandes de n. Para abordar esta situación, utilice los conceptos de multiplicación de módulo y división de módulo para lograr optimizaciones en términos de desbordamiento de enteros.

Averigüemos cómo construir Pascal Triangle para el mismo.

La declaración de array 1D se puede optimizar aún más con solo la declaración de una sola variable para realizar cálculos. Sin embargo, el desbordamiento de enteros también exige otras funciones para la implementación final.

La publicación a continuación menciona la implementación optimizada de espacio y tiempo para el cálculo del coeficiente binario.

// C++ program to find the nCr%p
// based on optimal Dynamic
// Programming implementation and
// Pascal Triangle concepts
#include <bits/stdc++.h>
using namespace std;
 
// Returns (a * b) % mod
long long moduloMultiplication(long long a, long long b,
                               long long mod)
{
 
    // Initialize result
    long long res = 0;
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b) {
 
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
        b >>= 1; // b = b / 2
    }
    return res;
}
 
// C++ function for extended Euclidean Algorithm
long long int gcdExtended(long long int a, long long int b,
                          long long int* x,
                          long long int* y);
 
// Function to find modulo inverse of b. It returns
// -1 when inverse doesn't exists
long long int modInverse(long long int b, long long int m)
{
 
    long long int x, y; // used in extended GCD algorithm
    long long int g = gcdExtended(b, m, &x, &y);
 
    // Return -1 if b and m are not co-prime
    if (g != 1)
        return -1;
 
    // m is added to handle negative x
    return (x % m + m) % m;
}
 
// C function for extended Euclidean Algorithm (used to
// find modular inverse.
long long int gcdExtended(long long int a, long long int b,
                          long long int* x,
                          long long int* y)
{
 
    // Base Case
    if (a == 0) {
        *x = 0, *y = 1;
        return b;
    }
 
    // To store results of recursive call
    long long int x1, y1;
 
    long long int gcd = gcdExtended(b % a, a, &x1, &y1);
 
    // Update x and y using results of recursive
    // call
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
 
// Function to compute a/b under modulo m
long long int modDivide(long long int a, long long int b,
                        long long int m)
{
 
    a = a % m;
    long long int inv = modInverse(b, m);
    if (inv == -1)
        // cout << "Division not defined";
        return 0;
    else
        return (inv * a) % m;
}
 
// Function to calculate nCr % p
int nCr(int n, int r, int p)
{
 
    // Edge Case which is not possible
    if (r > n)
        return 0;
 
    // Optimization for the cases when r is large
    if (r > n - r)
        r = n - r;
 
    // x stores the current result at
    long long int x = 1;
   
    // each iteration
    // Initialized to 1 as nC0 is always 1.
    for (int i = 1; i <= r; i++) {
 
        // Formula derived for calculating result is
        // C(n,r-1)*(n-r+1)/r
        // Function calculates x*(n-i+1) % p.
        x = moduloMultiplication(x, (n + 1 - i), p);
       
        // Function calculates x/i % p.
        x = modDivide(x, i, p);
    }
    return x;
}
 
// Driver Code
int main()
{
 
    long long int n = 5, r = 3, p = 1000000007;
    cout << "Value of nCr % p is " << nCr(n, r, p);
    return 0;
}

# Python3 program to find the nCr%p
# based on optimal Dynamic
# Programming implementation and
# Pascal Triangle concepts
 
# Returns (a * b) % mod
def moduloMultiplication(a, b, mod):
    # Initialize result
    res = 0
 
    # Update a if it is more than
    # or equal to mod
    a %= mod
 
    while (b):
 
        # If b is odd, add a with result
        if (b & 1):
            res = (res + a) % mod
 
        # Here we assume that doing 2*a
        # doesn't cause overflow
        a = (2 * a) % mod
        b >>= 1    # b = b / 2
 
    return res
 
 
# Global Variables
x, y = 0, 1
 
# Function for extended Euclidean Algorithm
 
 
def gcdExtended(a, b):
    global x, y
 
    # Base Case
    if (a == 0):
 
        x = 0
        y = 1
        return b
 
    # To store results of recursive call
    gcd = gcdExtended(b % a, a)
    x1 = x
    y1 = y
 
    # Update x and y using results of recursive
    # call
    x = y1 - int(b / a) * x1
    y = x1
 
    return gcd
 
 
def modInverse(a, m):
 
    g = gcdExtended(a, m)
 
    # Return -1 if b and m are not co-prime
    if (g != 1):
        return -1
 
    # m is added to handle negative x
    return (x % m + m) % m
 
 
# Function to compute a/b under modulo m
def modDivide(a, b, m):
 
    a = a % m
    inv = modInverse(b, m)
    if (inv == -1):
        return 0
    else:
        return (inv * a) % m
 
 
# Function to calculate nCr % p
def nCr(n, r, p):
 
    # Edge Case which is not possible
    if (r > n):
        return 0
 
    # Optimization for the cases when r is large
    if (r > n - r):
        r = n - r
 
    # x stores the current result at
    x = 1
 
    # each iteration
    # Initialized to 1 as nC0 is always 1.
    for i in range(1, r + 1):
 
        # Formula derived for calculating result is
        # C(n,r-1)*(n-r+1)/r
        # Function calculates x*(n-i+1) % p.
        x = moduloMultiplication(x, (n + 1 - i), p)
 
        # Function calculates x/i % p.
        x = modDivide(x, i, p)
 
    return x
 
# Driver Code
n = 5
r = 3
p = 1000000007
print("Value of nCr % p is ", nCr(n, r, p))
 
# This code is contributed by phasing17

// C# program to find the nCr%p
// based on optimal Dynamic
// Programming implementation and
// Pascal Triangle concepts
using System;
using System.Collections.Generic;
 
class GFG
{
  // Returns (a * b) % mod
  static long moduloMultiplication(long a, long b, long mod)
  {
    // Initialize result
    long res = 0;
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b > 0) {
 
      // If b is odd, add a with result
      if ((b & 1) != 0)
        res = (res + a) % mod;
 
      // Here we assume that doing 2*a
      // doesn't cause overflow
      a = (2 * a) % mod;
      b >>= 1; // b = b / 2
    }
    return res;
  }
 
  // Global Variables
  static long x, y;
 
  // Function for extended Euclidean Algorithm
  static long gcdExtended(long a, long b){
 
    // Base Case
    if (a == 0)
    {
      x = 0;
      y = 1;
      return b;
    }
 
    // To store results of recursive call  
    long gcd = gcdExtended(b % a, a);
    long x1 = x;
    long y1 = y;
 
    // Update x and y using results of recursive
    // call
    x = y1 - (b / a) * x1;
    y = x1;
 
    return gcd;
  }
 
  static long modInverse(long a, long m)
  {
    long g = gcdExtended(a, m);
 
    // Return -1 if b and m are not co-prime
    if (g != 1)
      return -1;
 
    // m is added to handle negative x
    return (x % m + m) % m;
  }
 
  // Function to compute a/b under modulo m
  static long modDivide(long a, long b, long m)
  {
 
    a = a % m;
    long inv = modInverse(b, m);
    if (inv == -1)
      return 0;
    else
      return (inv * a) % m;
  }
 
  // Function to calculate nCr % p
  static long nCr(long n, long r, long p)
  {
 
    // Edge Case which is not possible
    if (r > n)
      return 0;
 
    // Optimization for the cases when r is large
    if (r > n - r)
      r = n - r;
 
    // x stores the current result at
    long x = 1;
 
    // each iteration
    // Initialized to 1 as nC0 is always 1.
    for (long i = 1L; i <= r; i++) {
 
      // Formula derived for calculating result is
      // C(n,r-1)*(n-r+1)/r
      // Function calculates x*(n-i+1) % p.
      x = moduloMultiplication(x, (n + 1L - i), p);
 
      // Function calculates x/i % p.
      x = modDivide(x, i, p);
    }
    return x;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    long n = 5, r = 3, p = 1000000007;
    Console.Write("Value of nCr % p is " + nCr(n, r, p));
  }
}
 
// This code is contributed by phasing17

// JavaScript program to find the nCr%p
// based on optimal Dynamic
// Programming implementation and
// Pascal Triangle concepts
 
// Returns (a * b) % mod
function moduloMultiplication(a, b, mod)
{
    // Initialize result
    let res = 0;
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b) {
 
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
        b >>= 1; // b = b / 2
    }
    return res;
}
 
// Global Variables
let x, y;
  
// Function for extended Euclidean Algorithm
function gcdExtended(a, b){
       
    // Base Case
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
       
    // To store results of recursive call  
    let gcd = gcdExtended(b % a, a);
    let x1 = x;
    let y1 = y;
  
    // Update x and y using results of recursive
    // call
    x = y1 - Math.floor(b / a) * x1;
    y = x1;
   
    return gcd;
}
  
function modInverse(a, m)
{
    let g = gcdExtended(a, m);
     
    // Return -1 if b and m are not co-prime
    if (g != 1)
        return -1;
 
    // m is added to handle negative x
    return (x % m + m) % m;
}
 
// Function to compute a/b under modulo m
function modDivide(a, b, m)
{
 
    a = a % m;
    let inv = modInverse(b, m);
    if (inv == -1)
        return 0;
    else
        return (inv * a) % m;
}
 
// Function to calculate nCr % p
function nCr(n, r, p)
{
 
    // Edge Case which is not possible
    if (r > n)
        return 0;
 
    // Optimization for the cases when r is large
    if (r > n - r)
        r = n - r;
 
    // x stores the current result at
    let x = 1;
   
    // each iteration
    // Initialized to 1 as nC0 is always 1.
    for (var i = 1; i <= r; i++) {
 
        // Formula derived for calculating result is
        // C(n,r-1)*(n-r+1)/r
        // Function calculates x*(n-i+1) % p.
        x = moduloMultiplication(x, (n + 1 - i), p);
       
        // Function calculates x/i % p.
        x = modDivide(x, i, p);
    }
    return x;
}
 
// Driver Code
let n = 5, r = 3, p = 1000000007;
console.log("Value of nCr % p is ", nCr(n, r, p));
 
 
// This code is contributed by phasing17

Value of nCr % p is 10

Análisis de Complejidad:

• El código anterior necesita un espacio adicional de O(1) para los cálculos.
• El tiempo involucrado en el cálculo de nCr % p es del orden O(n).

Este artículo ha sido mejorado por Aryan Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.