Las siguientes son las definiciones comunes de coeficientes binomiales .
Un coeficiente binomial C(n, k) se puede definir como el coeficiente de x^k en la expansión de (1 + x)^n.
Un coeficiente binomial C(n, k) también da el número de formas, sin tener en cuenta el orden, en que pueden elegirse k objetos entre n objetos. De manera más formal, el número de subconjuntos de k elementos (o k combinaciones) de un elemento n establecer.
El problema
Escriba una función que tome dos parámetros n y k y devuelva el valor del coeficiente binomial C(n, k). Por ejemplo, su función debería devolver 6 para n = 4 y k = 2, y debería devolver 10 para n = 5 y k = 2 .1) Subestructura óptima
El valor de C(n, k) se puede calcular recursivamente utilizando la siguiente fórmula estándar para coeficientes binomiales.C(n, k) = C(n-1, k-1) + C(n-1, k) C(n, 0) = C(n, n) = 1La siguiente es una implementación recursiva simple que simplemente sigue la estructura recursiva mencionada anteriormente.
C++
// A naive recursive C++ implementation
#include <bits/stdc++.h>
using
namespace
std;
// Returns value of Binomial Coefficient C(n, k)
int
binomialCoeff(
int
n,
int
k)
{
// Base Cases
if
(k > n)
return
0;
if
(k == 0 || k == n)
return
1;
// Recur
return
binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}
/* Driver code*/
int
main()
{
int
n = 5, k = 2;
cout <<
"Value of C("
<< n <<
", "
<< k <<
") is "
<< binomialCoeff(n, k);
return
0;
}
// This is code is contributed by rathbhupendra
C
// A Naive Recursive Implementation
#include <stdio.h>
// Returns value of Binomial Coefficient C(n, k)
int
binomialCoeff(
int
n,
int
k)
{
// Base Cases
if
(k > n)
return
0;
if
(k == 0 || k == n)
return
1;
// Recur
return
binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}
/* Driver program to test above function*/
int
main()
{
int
n = 5, k = 2;
printf
(
"Value of C(%d, %d) is %d "
, n, k,
binomialCoeff(n, k));
return
0;
}
Java
// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import
java.util.*;
class
GFG {
// Returns value of Binomial
// Coefficient C(n, k)
static
int
binomialCoeff(
int
n,
int
k)
{
// Base Cases
if
(k > n)
return
0
;
if
(k ==
0
|| k == n)
return
1
;
// Recur
return
binomialCoeff(n -
1
, k -
1
)
+ binomialCoeff(n -
1
, k);
}
/* Driver program to test above function */
public
static
void
main(String[] args)
{
int
n =
5
, k =
2
;
System.out.printf(
"Value of C(%d, %d) is %d "
, n, k,
binomialCoeff(n, k));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# A naive recursive Python implementation
def
binomialCoeff(n, k):
if
k > n:
return
0
if
k
=
=
0
or
k
=
=
n:
return
1
# Recursive Call
return
binomialCoeff(n
-
1
, k
-
1
)
+
binomialCoeff(n
-
1
, k)
# Driver Program to test ht above function
n
=
5
k
=
2
(
"Value of C(%d,%d) is (%d)"
%
(n, k,
binomialCoeff(n, k)))
# This code is contributed by Nikhil Kumar Singh (nickzuck_007)
C#
// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using
System;
class
GFG {
// Returns value of Binomial
// Coefficient C(n, k)
static
int
binomialCoeff(
int
n,
int
k)
{
// Base Cases
if
(k > n)
return
0;
if
(k == 0 || k == n)
return
1;
// Recur
return
binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}
/* Driver program to test above function */
public
static
void
Main()
{
int
n = 5, k = 2;
Console.Write(
"Value of C("
+ n +
","
+ k +
") is "
+ binomialCoeff(n, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
// Returns value of
// Binomial Coefficient C(n, k)
function
binomialCoeff(
$n
,
$k
)
{
// Base Cases
if
(
$k
>
$n
)
return
0;
if
(
$k
==0 ||
$k
==
$n
)
return
1;
// Recur
return
binomialCoeff(
$n
- 1,
$k
- 1) +
binomialCoeff(
$n
- 1,
$k
);
}
// Driver Code
$n
= 5;
$k
= 2;
echo
"Value of C"
,
"("
,
$n
,
$k
,
") is "
, binomialCoeff(
$n
,
$k
);
// This code is contributed by aj_36
?>
JavaScript
<script>
// javascript Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
// Returns value of Binomial
// Coefficient C(n, k)
function
binomialCoeff(n , k)
{
// Base Cases
if
(k > n)
return
0;
if
(k == 0 || k == n)
return
1;
// Recur
return
binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}
/* Driver program to test above function */
var
n = 5, k = 2;
document.write(
"Value of C("
+n+
", "
+k+
") is "
+binomialCoeff(n, k));
// This code is contributed by Amit Katiyar
</script>
ProducciónValue of C(5, 2) is 10Complejidad del tiempo: O(n*max(k,nk))
Espacio auxiliar: O(n*max(k,nk))
2) Subproblemas superpuestos
Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez. Vea el siguiente árbol de recursión para n = 5 an k = 2. La función C(3, 1) se llama dos veces. Para valores grandes de n, habrá muchos subproblemas comunes.
Dado que se vuelven a llamar los mismos subproblemas, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema del coeficiente binomial tiene las dos propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de Programación Dinámica (DP) , los nuevos cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array 2D temporal C[][] de forma ascendente. A continuación se muestra la implementación basada en la programación dinámica.
C++
// A Dynamic Programming based solution that uses
// table C[][] to calculate the Binomial Coefficient
#include <bits/stdc++.h>
using
namespace
std;
// Prototype of a utility function that
// returns minimum of two integers
int
min(
int
a,
int
b);
// Returns value of Binomial Coefficient C(n, k)
int
binomialCoeff(
int
n,
int
k)
{
int
C[n + 1][k + 1];
int
i, j;
// Calculate value of Binomial Coefficient
// in bottom up manner
for
(i = 0; i <= n; i++) {
for
(j = 0; j <= min(i, k); j++) {
// Base Cases
if
(j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously
// stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return
C[n][k];
}
// A utility function to return
// minimum of two integers
int
min(
int
a,
int
b) {
return
(a < b) ? a : b; }
// Driver Code
int
main()
{
int
n = 5, k = 2;
cout <<
"Value of C["
<< n <<
"]["
<< k <<
"] is "
<< binomialCoeff(n, k);
}
// This code is contributed by Shivi_Aggarwal
C
// A Dynamic Programming based solution
// that uses table C[][] to
// calculate the Binomial Coefficient
#include <stdio.h>
// Prototype of a utility function that
// returns minimum of two integers
int
min(
int
a,
int
b);
// Returns value of Binomial Coefficient C(n, k)
int
binomialCoeff(
int
n,
int
k)
{
int
C[n + 1][k + 1];
int
i, j;
// Calculate value of Binomial Coefficient
// in bottom up manner
for
(i = 0; i <= n; i++) {
for
(j = 0; j <= min(i, k); j++) {
// Base Cases
if
(j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return
C[n][k];
}
// A utility function to return
// minimum of two integers
int
min(
int
a,
int
b) {
return
(a < b) ? a : b; }
/* Drier program to test above function*/
int
main()
{
int
n = 5, k = 2;
printf
(
"Value of C(%d, %d) is %d "
, n, k,
binomialCoeff(n, k));
return
0;
}
Java
// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient
class
BinomialCoefficient {
// Returns value of Binomial
// Coefficient C(n, k)
static
int
binomialCoeff(
int
n,
int
k)
{
int
C[][] =
new
int
[n +
1
][k +
1
];
int
i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for
(i =
0
; i <= n; i++) {
for
(j =
0
; j <= min(i, k); j++) {
// Base Cases
if
(j ==
0
|| j == i)
C[i][j] =
1
;
// Calculate value using
// previously stored values
else
C[i][j] = C[i -
1
][j -
1
] + C[i -
1
][j];
}
}
return
C[n][k];
}
// A utility function to return
// minimum of two integers
static
int
min(
int
a,
int
b) {
return
(a < b) ? a : b; }
/* Driver program to test above function*/
public
static
void
main(String args[])
{
int
n =
5
, k =
2
;
System.out.println(
"Value of C("
+ n +
","
+ k
+
") is "
+ binomialCoeff(n, k));
}
}
/*This code is contributed by Rajat Mishra*/
Python3
# A Dynamic Programming based Python
# Program that uses table C[][]
# to calculate the Binomial Coefficient
# Returns value of Binomial Coefficient C(n, k)
def
binomialCoef(n, k):
C
=
[[
0
for
x
in
range
(k
+
1
)]
for
x
in
range
(n
+
1
)]
# Calculate value of Binomial
# Coefficient in bottom up manner
for
i
in
range
(n
+
1
):
for
j
in
range
(
min
(i, k)
+
1
):
# Base Cases
if
j
=
=
0
or
j
=
=
i:
C[i][j]
=
1
# Calculate value using
# previously stored values
else
:
C[i][j]
=
C[i
-
1
][j
-
1
]
+
C[i
-
1
][j]
return
C[n][k]
# Driver program to test above function
n
=
5
k
=
2
(
"Value of C["
+
str
(n)
+
"]["
+
str
(k)
+
"] is "
+
str
(binomialCoef(n, k)))
# This code is contributed by Bhavya Jain
C#
// A Dynamic Programming based solution that
// uses table C[][] to calculate the Binomial
// Coefficient
using
System;
class
GFG {
// Returns value of Binomial Coefficient
// C(n, k)
static
int
binomialCoeff(
int
n,
int
k)
{
int
[, ] C =
new
int
[n + 1, k + 1];
int
i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for
(i = 0; i <= n; i++) {
for
(j = 0; j <= Math.Min(i, k); j++) {
// Base Cases
if
(j == 0 || j == i)
C[i, j] = 1;
// Calculate value using previously
// stored values
else
C[i, j] = C[i - 1, j - 1] + C[i - 1, j];
}
}
return
C[n, k];
}
// A utility function to return minimum
// of two integers
static
int
min(
int
a,
int
b) {
return
(a < b) ? a : b; }
/* Driver program to test above function*/
public
static
void
Main()
{
int
n = 5, k = 2;
Console.WriteLine(
"Value of C("
+ n +
","
+ k
+
") is "
+ binomialCoeff(n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient
// Returns value of Binomial
// Coefficient C(n, k)
function
binomialCoeff(
$n
,
$k
)
{
$C
=
array
(
array
());
$i
;
$j
;
// Calculate value of Binomial
// Coefficient in bottom up manner
for
(
$i
= 0;
$i
<=
$n
;
$i
++)
{
for
(
$j
= 0;
$j
<= min(
$i
,
$k
);
$j
++)
{
// Base Cases
if
(
$j
== 0 ||
$j
==
$i
)
$C
[
$i
][
$j
] = 1;
// Calculate value using
// previously stored values
else
$C
[
$i
][
$j
] =
$C
[
$i
- 1][
$j
- 1] +
$C
[
$i
- 1][
$j
];
}
}
return
$C
[
$n
][
$k
];
}
// Driver Code
$n
= 5;
$k
= 2;
echo
"Value of C("
,
$n
,
" "
,
$k
,
") is"
,
" "
, binomialCoeff(
$n
,
$k
) ;
// This code is contributed by anuj_67.
?>
JavaScript
<script>
// A Dynamic Programming based
// solution that uses table C to
// calculate the Binomial Coefficient
// Returns value of Binomial
// Coefficient C(n, k)
function
binomialCoeff(n, k)
{
var
C = Array(n + 1).fill(0).map(
x => Array(k + 1).fill(0));;
var
i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for
(i = 0; i <= n; i++)
{
for
(j = 0; j <= min(i, k); j++)
{
// Base Cases
if
(j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return
C[n][k];
}
// A utility function to return
// minimum of two integers
function
min(a, b)
{
return
(a < b) ? a : b;
}
// Driver code
var
n = 5, k = 2;
document.write(
"Value of C("
+ n +
","
+ k +
") is "
+ binomialCoeff(n, k));
// This code is contributed by 29AjayKumar
</script>
ProducciónValue of C[5][2] is 10Complejidad temporal: O(n*k)
Espacio auxiliar: O(n*k)A continuación se muestra una versión optimizada para el espacio del código anterior. El siguiente código solo usa O(k). Gracias a AK por sugerir este método.
C++
// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include <bits/stdc++.h>
using
namespace
std;
int
binomialCoeff(
int
n,
int
k)
{
int
C[k + 1];
memset
(C, 0,
sizeof
(C));
C[0] = 1;
// nC0 is 1
for
(
int
i = 1; i <= n; i++)
{
// Compute next row of pascal triangle using
// the previous row
for
(
int
j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return
C[k];
}
/* Driver code*/
int
main()
{
int
n = 5, k = 2;
cout <<
"Value of C("
<< n <<
","
<< k <<
")"
<<
"is "
<<binomialCoeff(n, k);
return
0;
}
// This code is contributed by shivanisinghss2110
C
// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include <stdio.h>
int
binomialCoeff(
int
n,
int
k)
{
int
C[k + 1];
memset
(C, 0,
sizeof
(C));
C[0] = 1;
// nC0 is 1
for
(
int
i = 1; i <= n; i++) {
// Compute next row of pascal triangle using
// the previous row
for
(
int
j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return
C[k];
}
/* Driver code*/
int
main()
{
int
n = 5, k = 2;
printf
(
"Value of C(%d, %d) is %d "
, n, k,
binomialCoeff(n, k));
return
0;
}
Java
// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import
java.util.*;
class
GFG {
static
int
binomialCoeff(
int
n,
int
k)
{
int
C[] =
new
int
[k +
1
];
// nC0 is 1
C[
0
] =
1
;
for
(
int
i =
1
; i <= n; i++) {
// Compute next row of pascal
// triangle using the previous row
for
(
int
j = Math.min(i, k); j >
0
; j--)
C[j] = C[j] + C[j -
1
];
}
return
C[k];
}
/* Driver code */
public
static
void
main(String[] args)
{
int
n =
5
, k =
2
;
System.out.printf(
"Value of C(%d, %d) is %d "
, n, k,
binomialCoeff(n, k));
}
}
Python3
# Python program for Optimized
# Dynamic Programming solution to
# Binomial Coefficient. This one
# uses the concept of pascal
# Triangle and less memory
def
binomialCoeff(n, k):
# Declaring an empty array
C
=
[
0
for
i
in
range
(k
+
1
)]
C[
0
]
=
1
# since nC0 is 1
for
i
in
range
(
1
, n
+
1
):
# Compute next row of pascal triangle using
# the previous row
j
=
min
(i, k)
while
(j >
0
):
C[j]
=
C[j]
+
C[j
-
1
]
j
-
=
1
return
C[k]
# Driver Code
n
=
5
k
=
2
(
"Value of C(%d,%d) is %d"
%
(n, k, binomialCoeff(n, k)))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using
System;
class
GFG {
static
int
binomialCoeff(
int
n,
int
k)
{
int
[] C =
new
int
[k + 1];
// nC0 is 1
C[0] = 1;
for
(
int
i = 1; i <= n; i++) {
// Compute next row of pascal
// triangle using the previous
// row
for
(
int
j = Math.Min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return
C[k];
}
/* Driver Code */
public
static
void
Main()
{
int
n = 5, k = 2;
Console.WriteLine(
"Value of C("
+ n +
" "
+ k
+
") is "
+ binomialCoeff(n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program for space optimized
// Dynamic Programming Solution of
// Binomial Coefficient
function
binomialCoeff(
$n
,
$k
)
{
$C
=
array_fill
(0,
$k
+ 1, 0);
$C
[0] = 1;
// nC0 is 1
for
(
$i
= 1;
$i
<=
$n
;
$i
++)
{
// Compute next row of pascal
// triangle using the previous row
for
(
$j
= min(
$i
,
$k
);
$j
> 0;
$j
--)
$C
[
$j
] =
$C
[
$j
] +
$C
[
$j
- 1];
}
return
$C
[
$k
];
}
// Driver Code
$n
= 5;
$k
= 2;
echo
"Value of C[$n, $k] is "
.
binomialCoeff(
$n
,
$k
);
// This code is contributed by mits.
?>
JavaScript
<script>
// Javascript program for space optimized
// Dynamic Programming
// Solution of Binomial Coefficient
function
binomialCoeff(n, k)
{
let C =
new
Array(k + 1);
C.fill(0);
// nC0 is 1
C[0] = 1;
for
(let i = 1; i <= n; i++)
{
// Compute next row of pascal
// triangle using the previous
// row
for
(let j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return
C[k];
}
// Driver code
let n = 5, k = 2;
document.write(
"Value of C("
+ n +
" "
+
k +
") is "
+ binomialCoeff(n, k));
// This code is contributed by divyesh072019
</script>
ProducciónValue of C(5, 2) is 10Complejidad temporal: O(n*k)
Espacio auxiliar: O(k)Explicación:
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 del triángulo pascal, usando (i-1)-ésima fila
En cualquier momento, cada elemento de la array C tendrá algún valor (CERO o más) y en la siguiente iteración, el valor de esos elementos proviene de la iteración anterior.
En declaración,
C[j] = C[j] + C[j-1]
El lado derecho representa el valor proveniente de la iteración anterior (una fila del triángulo de Pascal depende de la fila anterior). El lado izquierdo representa el valor de la iteración actual que se obtendrá con esta declaración.Let's say we want to calculate C(4, 3), i.e. n=4, k=3: All elements of array C of size 4 (k+1) are initialized to ZERO. i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0; Then C[0] is set to 1 For i = 1: C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1 For i = 2: C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1 C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,1) = 2 For i=3: C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1 C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3 C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3 For i=4: C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1 C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4 C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6 C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4 C(4,3) = 4 is would be the answer in our example.Enfoque de memorización: la idea es crear una tabla de búsqueda y seguir el enfoque recursivo de arriba hacia abajo. Antes de calcular cualquier valor, verificamos si ya está en la tabla de búsqueda. Si es así, devolvemos el valor. De lo contrario, calculamos el valor y lo almacenamos en la tabla de búsqueda. El siguiente es el enfoque de arriba hacia abajo de la programación dinámica para encontrar el valor del coeficiente binomial.
C++
// A Dynamic Programming based
// solution that uses
// table dp[][] to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table C++ implementation
#include <bits/stdc++.h>
using
namespace
std;
// Returns value of Binomial Coefficient C(n, k)
int
binomialCoeffUtil(
int
n,
int
k,
int
** dp)
{
// If value in lookup table then return
if
(dp[n][k] != -1)
//
return
dp[n][k];
// store value in a table before return
if
(k == 0) {
dp[n][k] = 1;
return
dp[n][k];
}
// store value in table before return
if
(k == n) {
dp[n][k] = 1;
return
dp[n][k];
}
// save value in lookup table before return
dp[n][k] = binomialCoeffUtil(n - 1, k - 1, dp) +
binomialCoeffUtil(n - 1, k, dp);
return
dp[n][k];
}
int
binomialCoeff(
int
n,
int
k)
{
int
** dp;
// make a temporary lookup table
dp =
new
int
*[n + 1];
// loop to create table dynamically
for
(
int
i = 0; i < (n + 1); i++) {
dp[i] =
new
int
[k + 1];
}
// nested loop to initialise the table with -1
for
(
int
i = 0; i < (n + 1); i++) {
for
(
int
j = 0; j < (k + 1); j++) {
dp[i][j] = -1;
}
}
return
binomialCoeffUtil(n, k, dp);
}
/* Driver code*/
int
main()
{
int
n = 5, k = 2;
cout <<
"Value of C("
<< n <<
", "
<< k <<
") is "
<< binomialCoeff(n, k) << endl;
return
0;
}
// This is code is contributed by MOHAMMAD MUDASSIR
Java
// A Dynamic Programming based
// solution that uses
// table dp[][] to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table Java implementation
import
java.util.*;
class
GFG{
// Returns value of Binomial
// Coefficient C(n, k)
static
int
binomialCoeffUtil(
int
n,
int
k,
Vector<Integer> []dp)
{
// If value in lookup table
// then return
if
(dp[n].get(k) != -
1
)
return
dp[n].get(k);
// store value in a table
// before return
if
(k ==
0
)
{
dp[n].add(k,
1
);
return
dp[n].get(k);
}
// store value in table
// before return
if
(k == n)
{
dp[n].add(k,
1
);
return
dp[n].get(k);
}
// save value in lookup table
// before return
dp[n].add(k, binomialCoeffUtil(n -
1
,
k -
1
, dp) +
binomialCoeffUtil(n -
1
,
k, dp));
return
dp[n].get(k);
}
static
int
binomialCoeff(
int
n,
int
k)
{
// Make a temporary lookup table
Vector<Integer> []dp =
new
Vector[n+
1
];
// Loop to create table dynamically
for
(
int
i =
0
; i < (n +
1
); i++)
{
dp[i] =
new
Vector<Integer>();
for
(
int
j =
0
; j <= k; j++)
dp[i].add(-
1
);
}
return
binomialCoeffUtil(n, k, dp);
}
// Driver code
public
static
void
main(String[] args)
{
int
n =
5
, k =
2
;
System.out.print(
"Value of C("
+ n +
", "
+ k +
") is "
+
binomialCoeff(n, k) +
"\n"
);
}
}
// This code is contributed by Rajput-Ji
Python3
# A Dynamic Programming based solution
# that uses table dp[][] to calculate
# the Binomial Coefficient. A naive
# recursive approach with table
# Python3 implementation
# Returns value of Binomial
# Coefficient C(n, k)
def
binomialCoeffUtil(n, k, dp):
# If value in lookup table then return
if
dp[n][k] !
=
-
1
:
return
dp[n][k]
# Store value in a table before return
if
k
=
=
0
:
dp[n][k]
=
1
return
dp[n][k]
# Store value in table before return
if
k
=
=
n:
dp[n][k]
=
1
return
dp[n][k]
# Save value in lookup table before return
dp[n][k]
=
(binomialCoeffUtil(n
-
1
, k
-
1
, dp)
+
binomialCoeffUtil(n
-
1
, k, dp))
return
dp[n][k]
def
binomialCoeff(n, k):
# Make a temporary lookup table
dp
=
[ [
-
1
for
y
in
range
(k
+
1
) ]
for
x
in
range
(n
+
1
) ]
return
binomialCoeffUtil(n, k, dp)
# Driver code
n
=
5
k
=
2
(
"Value of C("
+
str
(n)
+
", "
+
str
(k)
+
") is"
,
binomialCoeff(n, k))
# This is code is contributed by Prateek Gupta
C#
// C# program for the
// above approach
// A Dynamic Programming based
// solution that uses
// table [,]dp to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table C# implementation
using
System;
using
System.Collections.Generic;
class
GFG{
// Returns value of Binomial
// Coefficient C(n, k)
static
int
binomialCoeffUtil(
int
n,
int
k,
List<
int
> []dp)
{
// If value in lookup table
// then return
if
(dp[n][k] != -1)
return
dp[n][k];
// store value in a table
// before return
if
(k == 0)
{
dp[n][k] = 1;
return
dp[n][k];
}
// store value in table
// before return
if
(k == n)
{
dp[n][k] = 1;
return
dp[n][k];
}
// save value in lookup table
// before return
dp[n][k] = binomialCoeffUtil(n - 1,
k - 1, dp) +
binomialCoeffUtil(n - 1,
k, dp);
return
dp[n][k];
}
static
int
binomialCoeff(
int
n,
int
k)
{
// Make a temporary lookup table
List<
int
> []dp =
new
List<
int
>[n + 1];
// Loop to create table dynamically
for
(
int
i = 0; i < (n + 1); i++)
{
dp[i] =
new
List<
int
>();
for
(
int
j = 0; j <= k; j++)
dp[i].Add(-1);
}
return
binomialCoeffUtil(n, k, dp);
}
// Driver code
public
static
void
Main(String[] args)
{
int
n = 5, k = 2;
Console.Write(
"Value of C("
+ n +
", "
+ k +
") is "
+
binomialCoeff(n, k) +
"\n"
);
}
}
// This code is contributed by 29AjayKumar
JavaScript
<script>
// A Dynamic Programming based solution that
// uses table dp[][] to calculate the
// Binomial Coefficient. A naive recursive
// approach with table Javascript implementation
// Returns value of Binomial
// Coefficient C(n, k)
function
binomialCoeffUtil(n, k, dp)
{
// If value in lookup table
// then return
if
(dp[n][k] != -1)
return
dp[n][k];
// Store value in a table
// before return
if
(k == 0)
{
dp[n][k] = 1;
return
dp[n][k];
}
// Store value in table
// before return
if
(k == n)
{
dp[n][k] = 1;
return
dp[n][k];
}
// Save value in lookup table
// before return
dp[n][k] = binomialCoeffUtil(n - 1,
k - 1, dp) +
binomialCoeffUtil(n - 1,
k, dp);
return
dp[n][k];
}
function
binomialCoeff(n, k)
{
// Make a temporary lookup table
let dp =
new
Array(n + 1);
// Loop to create table dynamically
for
(let i = 0; i < (n + 1); i++)
{
dp[i] = [];
for
(let j = 0; j <= k; j++)
dp[i].push(-1);
}
return
binomialCoeffUtil(n, k, dp);
}
// Driver code
let n = 5, k = 2;
document.write(
"Value of C("
+ n +
", "
+ k +
") is "
+
binomialCoeff(n, k) +
"\n"
);
// This code is contributed by avanitrachhadiya2155
</script>
Complejidad de tiempo: O(n*k)
Espacio Auxiliar: O(n*k)
ProducciónValue of C(5, 2) is 10Cancelación de factores entre numerador y denominador:
nCr = (n-r+1)*(n-r+2)*….*n / (r!)
Cree una array arr de números de n-r+1 a n que será de tamaño r. Como nCr siempre es un número entero, todos los números en el denominador deben cancelarse con el producto del numerador (representado por arr).
para i = 1 a i = r,
busque arr, si arr[j] y tengo gcd>1, divida ambos por el gcd y cuando se convierta en 1, detenga la búsqueda
Ahora, la respuesta es solo el producto de arr, cuyo valor mod 10^9+7 se puede encontrar usando un solo paso y la fórmula use (a*b)%mod = (a%mod * b%mod)%mod
C++
// C++ program to find gcd of
// two numbers in O(log(min(a,b)))
#include <bits/stdc++.h>
using
namespace
std;
int
gcd(
int
a,
int
b)
{
if
(b == 0)
return
a;
return
gcd(b, a % b);
}
int
nCr(
int
n,
int
r)
{
// base case
if
(r > n)
return
0;
// C(n,r) = C(n,n-r)
if
(r > n - r)
r = n - r;
int
mod = 1000000007;
// array of elements from n-r+1 to n
int
arr[r];
for
(
int
i = n - r + 1; i <= n; i++) {
arr[i + r - n - 1] = i;
}
long
int
ans = 1;
// for numbers from 1 to r find arr[j],
// such that gcd(i,arr[j])>1
for
(
int
k = 1; k < r + 1; k++) {
int
j = 0, i = k;
while
(j < r) {
int
x = gcd(i, arr[j]);
if
(x > 1) {
// if gcd>1, divide both by gcd
arr[j] /= x;
i /= x;
}
// if i becomes 1, no need to search arr
if
(i == 1)
break
;
j += 1;
}
}
// single pass to multiply the numerator
for
(
int
i : arr)
ans = (ans * i) % mod;
return
(
int
)ans;
}
int
main()
{
int
n = 5, r = 2;
cout <<
"Value of C("
<< n <<
", "
<< r <<
") is "
<< nCr(n, r) <<
"\n"
;
return
0;
}
// This code is contributed by rajsanghavi9.
Java
import
java.util.*;
class
GFG
{
static
int
gcd(
int
a,
int
b)
// function to find gcd of two numbers in O(log(min(a,b)))
{
if
(b==
0
)
return
a;
return
gcd(b,a%b);
}
static
int
nCr(
int
n,
int
r)
{
if
(r>n)
// base case
return
0
;
if
(r>n-r)
// C(n,r) = C(n,n-r) better time complexity for lesser r value
r = n-r;
int
mod =
1000000007
;
int
[] arr =
new
int
[r];
// array of elements from n-r+1 to n
for
(
int
i=n-r+
1
; i<=n; i++)
{
arr[i+r-n-
1
] = i;
}
long
ans =
1
;
for
(
int
k=
1
;k<r+
1
;k++)
// for numbers from 1 to r find arr[j] such that gcd(i,arr[j])>1
{
int
j=
0
, i=k;
while
(j<arr.length)
{
int
x = gcd(i,arr[j]);
if
(x>
1
)
{
arr[j] /= x;
// if gcd>1, divide both by gcd
i /= x;
}
if
(i==
1
)
break
;
// if i becomes 1, no need to search arr
j +=
1
;
}
}
for
(
int
i : arr)
// single pass to multiply the numerator
ans = (ans*i)%mod;
return
(
int
)ans;
}
// Driver code
public
static
void
main(String[] args)
{
int
n =
5
, r =
2
;
System.out.print(
"Value of C("
+ n+
", "
+ r+
") is "
+nCr(n, r) +
"\n"
);
}
}
// This code is contributed by Gautam Wadhwani
Python3
import
math
class
GFG:
def
nCr(
self
, n, r):
def
gcd(a,b):
# function to find gcd of two numbers in O(log(min(a,b)))
if
b
=
=
0
:
# base case
return
a
return
gcd(b,a
%
b)
if
r>n:
return
0
if
r>n
-
r:
# C(n,r) = C(n,n-r) better time complexity for lesser r value
r
=
n
-
r
mod
=
10
*
*
9
+
7
arr
=
list
(
range
(n
-
r
+
1
,n
+
1
))
# array of elements from n-r+1 to n
ans
=
1
for
i
in
range
(
1
,r
+
1
):
# for numbers from 1 to r find arr[j] such that gcd(i,arr[j])>1
j
=
0
while
j<
len
(arr):
x
=
gcd(i,arr[j])
if
x>
1
:
arr[j]
/
/
=
x
# if gcd>1, divide both by gcd
i
/
/
=
x
if
arr[j]
=
=
1
:
# if element becomes 1, its of no use anymore so delete from arr
del
arr[j]
j
-
=
1
if
i
=
=
1
:
break
# if i becomes 1, no need to search arr
j
+
=
1
for
i
in
arr:
# single pass to multiply the numerator
ans
=
(ans
*
i)
%
mod
return
ans
# Driver code
n
=
5
k
=
2
ob
=
GFG()
(
"Value of C("
+
str
(n)
+
", "
+
str
(k)
+
") is"
,
ob.nCr(n, k))
# This is code is contributed by Gautam Wadhwani
C#
using
System;
class
GFG{
// Function to find gcd of two numbers
// in O(log(min(a,b)))
static
int
gcd(
int
a,
int
b)
{
if
(b == 0)
return
a;
return
gcd(b, a % b);
}
static
int
nCr(
int
n,
int
r)
{
// Base case
if
(r > n)
return
0;
// C(n,r) = C(n,n-r) better time
// complexity for lesser r value
if
(r > n - r)
r = n - r;
int
mod = 1000000007;
// Array of elements from n-r+1 to n
int
[] arr =
new
int
[r];
for
(
int
i = n - r + 1; i <= n; i++)
{
arr[i + r - n - 1] = i;
}
long
ans = 1;
// For numbers from 1 to r find arr[j]
// such that gcd(i,arr[j])>1
for
(
int
k = 1; k < r + 1; k++)
{
int
j = 0, i = k;
while
(j < arr.Length)
{
int
x = gcd(i,arr[j]);
if
(x > 1)
{
// If gcd>1, divide both by gcd
arr[j] /= x;
i /= x;
}
if
(i == 1)
// If i becomes 1, no need
// to search arr
break
;
j += 1;
}
}
// Single pass to multiply the numerator
foreach
(
int
i
in
arr)
ans = (ans * i) % mod;
return
(
int
)ans;
}
// Driver code
static
public
void
Main()
{
int
n = 5, r = 2;
Console.WriteLine(
"Value of C("
+ n +
", "
+ r +
") is "
+
nCr(n, r) +
"\n"
);
}
}
// This code is contributed by rag2127
JavaScript
<script>
// Javascript program to find gcd of
// two numbers in O(log(min(a,b)))
function
gcd(a, b)
{
if
(b == 0)
return
a;
return
gcd(b, a % b);
}
function
nCr(n, r)
{
// Base case
if
(r > n)
return
0;
// C(n,r) = C(n,n-r) better time
// complexity for lesser r value
if
(r > n - r)
r = n - r;
mod = 1000000007;
// Array of elements from n-r+1 to n
var
arr =
new
Array(r);
for
(
var
i = n - r + 1; i <= n; i++)
{
arr[i + r - n - 1] = i;
}
var
ans = 1;
// For numbers from 1 to r find arr[j]
// such that gcd(i,arr[j])>1
for
(
var
k = 1; k < r + 1 ; k++)
{
var
j = 0, i = k;
while
(j < arr.length)
{
var
x = gcd(i, arr[j]);
if
(x > 1)
{
// If gcd>1, divide both by gcd
arr[j] /= x;
i /= x;
}
// If i becomes 1, no need to search arr
if
(i == 1)
break
;
j += 1;
}
}
// Single pass to multiply the numerator
arr.forEach(
function
(i)
{
ans = (ans * i) % mod;
});
return
ans;
}
// Driver code
var
n = 5, r = 2;
document.write(
"Value of C("
+ n +
", "
+
r +
") is "
+ nCr(n, r) +
"\n"
);
// This code is contributed by shivanisinghss2110
</script>
ProducciónValue of C(5, 2) is 10Complejidad de tiempo: O(( min(r, nr)^2 ) * log(n)), útil cuando n >> r o n >> (nr)
Espacio auxiliar: O(min(r, nr))
Ver esto para GCD en tiempo logarítmico
Factorización prima de todos los números del 1 al n usando la criba de Eratóstenes:
1. Cree una array SPF de tamaño n+1 al factor primo más pequeño de cada número de 1 a n
Set SPF[i] = i for all i = 1 to i = n2. Usar Tamiz de Eratóstenes:
for i = 2 to i = n: if i is prime, for all multiples j of i, j<=n: if SPF[j] equals j, set SPF[j] = i3. Una vez que sabemos el SPF de cada número del 1 al n, podemos encontrar la descomposición en factores primos de cualquier número del 1 al n en tiempo O(log(n)) usando la división recursiva por el SPF hasta que el número se convierte en 1
Now, nCr = (n-r+1)*(r+2)* ... *(n) / (r)!4. Cree un diccionario (o hashmap) para almacenar la frecuencia de cada número primo en la descomposición en factores primos del valor real de nCr.
5. Entonces, solo calcule la frecuencia de cada número primo en nCr y multiplíquelos elevados a la potencia de su frecuencia.
6. Para el numerador, itere a través de i = n-r+1 hasta i = n, y para todos los factores primos de i, almacene su frecuencia en un diccionario.
( prime_pow[prime_factor] += freq_in_i )7. Para el denominador, itere desde i = 1 hasta i = r y ahora reste la frecuencia en lugar de sumar.
8. Ahora, recorra el diccionario y multiplique la respuesta a (prime ^ prime_pow[prime]) % (10^9 + 7)
ans = (ans * pow(prime, prime_pow[prime], mod) ) % modC++
#include <bits/stdc++.h>
using
namespace
std;
// pow(base,exp,mod) is used to find
// (base^exp)%mod fast -> O(log(exp))
long
int
pow
(
long
int
b,
long
int
exp
,
long
int
mod)
{
long
int
ret = 1;
while
(
exp
> 0) {
if
((
exp
& 1) > 0)
ret = (ret * b) % mod;
b = (b * b) % mod;
exp
>>= 1;
}
return
ret;
}
int
nCr(
int
n,
int
r)
{
// base case
if
(r > n)
return
0;
// C(n,r) = C(n,n-r) Complexity for
// this code is lesser for lower n-r
if
(n - r > r)
r = n - r;
// list to smallest prime factor
// of each number from 1 to n
int
SPF[n + 1];
// set smallest prime factor of each
// number as itself
for
(
int
i = 1; i <= n; i++)
SPF[i] = i;
// set smallest prime factor of all
// even numbers as 2
for
(
int
i = 4; i <= n; i += 2)
SPF[i] = 2;
for
(
int
i = 3; i * i < n + 1; i += 2) {
// Check if i is prime
if
(SPF[i] == i) {
// All multiples of i are
// composite (and divisible by
// i) so add i to their prime
// factorization getpow(j,i)
// times
for
(
int
j = i * i; j < n + 1; j += i)
if
(SPF[j] == j) {
SPF[j] = i;
}
}
}
// Hash Map to store power of
// each prime in C(n,r)
map<
int
,
int
> prime_pow;
// For numerator count frequency of each prime factor
for
(
int
i = r + 1; i < n + 1; i++) {
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t > 1) {
if
(!prime_pow[SPF[t]]) {
prime_pow[SPF[t]] = 1;
}
else
prime_pow[SPF[t]]++;
// prime_pow.put(SPF[t],
// prime_pow.getOrDefault(SPF[t], 0)
// + 1);
t /= SPF[t];
}
}
// For denominator subtract the power of
// each prime factor
for
(
int
i = 1; i < n - r + 1; i++) {
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t > 1) {
prime_pow[SPF[t]]--;
// prime_pow.put(SPF[t],
// prime_pow.get(SPF[t]) - 1);
t /= SPF[t];
}
}
// long because mod is large and a%mod
// * b%mod can overflow int
long
int
ans = 1, mod = 1000000007;
// use (a*b)%mod = (a%mod * b%mod)%mod
for
(
auto
it : prime_pow)
// pow(base,exp,mod) is used to
// find (base^exp)%mod fast
ans = (ans
*
pow
(it.first, prime_pow[it.first], mod))
% mod;
return
(
int
)ans;
}
int
main()
{
int
n = 5, r = 2;
cout <<
"Value of C("
<< n <<
", "
<< r <<
") is "
<< nCr(n, r) <<
"\n"
;
return
0;
}
// This code is contributed by rajsanghavi9.
Java
import
java.util.*;
class
GFG {
// pow(base,exp,mod) is used to find
// (base^exp)%mod fast -> O(log(exp))
static
long
pow(
long
b,
long
exp,
long
mod)
{
long
ret =
1
;
while
(exp >
0
) {
if
((exp &
1
) >
0
)
ret = (ret * b) % mod;
b = (b * b) % mod;
exp >>=
1
;
}
return
ret;
}
static
int
nCr(
int
n,
int
r)
{
if
(r > n)
// base case
return
0
;
// C(n,r) = C(n,n-r) Complexity for
// this code is lesser for lower n-r
if
(n - r > r)
r = n - r;
// list to smallest prime factor
// of each number from 1 to n
int
[] SPF =
new
int
[n +
1
];
// set smallest prime factor of each
// number as itself
for
(
int
i =
1
; i <= n; i++)
SPF[i] = i;
// set smallest prime factor of all
// even numbers as 2
for
(
int
i =
4
; i <= n; i +=
2
)
SPF[i] =
2
;
for
(
int
i =
3
; i * i < n +
1
; i +=
2
)
{
// Check if i is prime
if
(SPF[i] == i)
{
// All multiples of i are
// composite (and divisible by
// i) so add i to their prime
// factorization getpow(j,i)
// times
for
(
int
j = i * i; j < n +
1
; j += i)
if
(SPF[j] == j) {
SPF[j] = i;
}
}
}
// Hash Map to store power of
// each prime in C(n,r)
Map<Integer, Integer> prime_pow
=
new
HashMap<>();
// For numerator count frequency of each prime factor
for
(
int
i = r +
1
; i < n +
1
; i++)
{
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t >
1
)
{
prime_pow.put(SPF[t],
prime_pow.getOrDefault(SPF[t],
0
) +
1
);
t /= SPF[t];
}
}
// For denominator subtract the power of
// each prime factor
for
(
int
i =
1
; i < n - r +
1
; i++)
{
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t >
1
)
{
prime_pow.put(SPF[t],
prime_pow.get(SPF[t]) -
1
);
t /= SPF[t];
}
}
// long because mod is large and a%mod
// * b%mod can overflow int
long
ans =
1
, mod =
1000000007
;
// use (a*b)%mod = (a%mod * b%mod)%mod
for
(
int
i : prime_pow.keySet())
// pow(base,exp,mod) is used to
// find (base^exp)%mod fast
ans = (ans * pow(i, prime_pow.get(i), mod))
% mod;
return
(
int
)ans;
}
// Driver code
public
static
void
main(String[] args)
{
int
n =
5
, r =
2
;
System.out.print(
"Value of C("
+ n +
", "
+ r
+
") is "
+ nCr(n, r) +
"\n"
);
}
}
// This code is contributed by Gautam Wadhwani
Python3
# Python code for the above approach
import
math
class
GFG:
def
nCr(
self
, n, r):
# Base case
if
r > n:
return
0
# C(n,r) = C(n,n-r) Complexity for this
# code is lesser for lower n-r
if
n
-
r > r:
r
=
n
-
r
# List to store smallest prime factor
# of every number from 1 to n
SPF
=
[i
for
i
in
range
(n
+
1
)]
for
i
in
range
(
4
, n
+
1
,
2
):
# set smallest prime factor of
# all even numbers as 2
SPF[i]
=
2
for
i
in
range
(
3
, n
+
1
,
2
):
if
i
*
i > n:
break
# Check if i is prime
if
SPF[i]
=
=
i:
# All multiples of i are composite
# (and divisible by i) so add i to
# their prime factorization getpow(j,i) times
for
j
in
range
(i
*
i, n
+
1
, i):
if
SPF[j]
=
=
j:
# set smallest prime factor
# of j to i only if it is
# not previously set
SPF[j]
=
i
# dictionary to store power of each prime in C(n,r)
prime_pow
=
{}
# For numerator count frequency
# of each prime factor
for
i
in
range
(r
+
1
, n
+
1
):
t
=
i
# Recursive division to
# find prime factorization of i
while
t >
1
:
if
not
SPF[t]
in
prime_pow:
prime_pow[SPF[t]]
=
1
else
:
prime_pow[SPF[t]]
+
=
1
t
/
/
=
SPF[t]
# For denominator subtract the
# power of each prime factor
for
i
in
range
(
1
, n
-
r
+
1
):
t
=
i
# Recursive division to
# find prime factorization of i
while
t >
1
:
prime_pow[SPF[t]]
-
=
1
t
/
/
=
SPF[t]
ans
=
1
mod
=
10
*
*
9
+
7
# Use (a*b)%mod = (a%mod * b%mod)%mod
for
i
in
prime_pow:
# pow(base,exp,mod) is used to
# find (base^exp)%mod fast
ans
=
(ans
*
pow
(i, prime_pow[i], mod))
%
mod
return
ans
# Driver code
n
=
5
k
=
2
ob
=
GFG()
(
"Value of C("
+
str
(n)
+
", "
+
str
(k)
+
") is"
,
ob.nCr(n, k))
# This is code is contributed by Gautam Wadhwani
C#
using
System;
using
System.Collections.Generic;
public
class
GFG {
// pow(base,exp,mod) is used to find
// (base^exp)%mod fast -> O(log(exp))
static
long
pow(
long
b,
long
exp,
long
mod)
{
long
ret = 1;
while
(exp > 0) {
if
((exp & 1) > 0)
ret = (ret * b) % mod;
b = (b * b) % mod;
exp >>= 1;
}
return
ret;
}
static
int
nCr(
int
n,
int
r)
{
if
(r > n)
// base case
return
0;
// C(n,r) = C(n,n-r) Complexity for
// this code is lesser for lower n-r
if
(n - r > r)
r = n - r;
// list to smallest prime factor
// of each number from 1 to n
int
[] SPF =
new
int
[n + 1];
// set smallest prime factor of each
// number as itself
for
(
int
i = 1; i <= n; i++)
SPF[i] = i;
// set smallest prime factor of all
// even numbers as 2
for
(
int
i = 4; i <= n; i += 2)
SPF[i] = 2;
for
(
int
i = 3; i * i < n + 1; i += 2) {
// Check if i is prime
if
(SPF[i] == i) {
// All multiples of i are
// composite (and divisible by
// i) so add i to their prime
// factorization getpow(j,i)
// times
for
(
int
j = i * i; j < n + 1; j += i)
if
(SPF[j] == j) {
SPF[j] = i;
}
}
}
// Hash Map to store power of
// each prime in C(n,r)
Dictionary<
int
,
int
> prime_pow
=
new
Dictionary<
int
,
int
>();
// For numerator count frequency of each prime
// factor
for
(
int
i = r + 1; i < n + 1; i++) {
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t > 1) {
if
(prime_pow.ContainsKey(SPF[t])) {
prime_pow[SPF[t]]
= prime_pow[SPF[t]] + 1;
}
else
{
prime_pow.Add(SPF[t], 1);
}
t /= SPF[t];
}
}
// For denominator subtract the power of
// each prime factor
for
(
int
i = 1; i < n - r + 1; i++) {
int
t = i;
// Recursive division to find
// prime factorization of i
while
(t > 1) {
if
(prime_pow.ContainsKey(SPF[t])) {
prime_pow[SPF[t]]
= prime_pow[SPF[t]] - 1;
}
t /= SPF[t];
}
}
// long because mod is large and a%mod
// * b%mod can overflow int
long
ans = 1, mod = 1000000007;
// use (a*b)%mod = (a%mod * b%mod)%mod
foreach
(
int
i
in
prime_pow.Keys)
// pow(base,exp,mod) is used to
// find (base^exp)%mod fast
ans
= (ans * pow(i, prime_pow[i], mod)) % mod;
return
(
int
)ans;
}
// Driver code
public
static
void
Main(String[] args)
{
int
n = 5, r = 2;
Console.Write(
"Value of C("
+ n +
", "
+ r +
") is "
+ nCr(n, r) +
"\n"
);
}
}
// This code contributed by gauravrajput1
JavaScript
<script>
// Javascript program to find gcd of
// two numbers in O(log(min(a,b)))
function
gcd(a, b)
{
if
(b == 0)
return
a;
return
gcd(b, a % b);
}
function
nCr(n, r)
{
// base case
if
(r > n)
return
0;
// C(n,r) = C(n,n-r)
if
(r > n - r)
r = n - r;
var
mod = 1000000007;
// array of elements from n-r+1 to n
var
arr =
new
Array(r);
for
(
var
i = n - r + 1; i <= n; i++) {
arr[i + r - n - 1] = i;
}
var
ans = 1;
// for numbers from 1 to r find arr[j],
// such that gcd(i,arr[j])>1
for
(
var
k = 1; k < r + 1; k++) {
var
j = 0;
var
i = k;
do
{
var
x = gcd(i, arr[j]);
if
(x > 1) {
// if gcd>1, divide both by gcd
arr[j] /= x;
i /= x;
}
// if i becomes 1, no need to search arr
if
(i == 1)
break
;
j += 1;
}
while
(j < r);
}
// single pass to multiply the numerator
arr.forEach(
function
(i, index) {
ans = (ans * i) % mod;
});
return
ans;
}
var
n = 5;
var
r = 2;
document.write(
"Value of C("
+ n +
", "
+ r +
") is "
+ nCr(n, r) +
"<br>"
);
// This code is contributed by shivani.
</script>
ProducciónValue of C(5, 2) is 10Complejidad de tiempo: O(n*log(n)), muy útil cuando r->n/2
Espacio Auxiliar: O(n)
Vea esto para la factorización prima en O (log (n))
Otro enfoque: (técnica de inversión modular)
1. La fórmula general de nCr es ( n*(n-1)*(n-2)* … *(n-r+1) ) / (r!). Podemos usar directamente esta fórmula para encontrar nCr. Pero eso se desbordará fuera de límite. Necesitamos encontrar nCr mod m para que no se desborde. Podemos hacerlo fácilmente con fórmula aritmética modular.
for the n*(n-1)*(n-2)* ... *(n-r+1) part we can use the formula, (a*b) mod m = ((a % m) * (b % m)) % m2. y para el 1/r! parte, necesitamos encontrar el inverso modular de cada número del 1 al r. Luego use la misma fórmula anterior con un inverso modular de 1 a r. Podemos encontrar el inverso modular en tiempo O(r) usando la fórmula,
inv[1] = 1 inv[i] = − ⌊m/i⌋ * inv[m mod i] mod m To use this formula, m has to be a prime.En el problema de práctica, necesitamos mostrar la respuesta con módulo 1000000007 que es un número primo.
Entonces, esta técnica funcionará.
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using
namespace
std;
// Function to find binomial
// coefficient
int
binomialCoeff(
int
n,
int
r)
{
if
(r > n)
return
0;
long
long
int
m = 1000000007;
long
long
int
inv[r + 1] = { 0 };
inv[0] = 1;
if
(r+1>=2)
inv[1] = 1;
// Getting the modular inversion
// for all the numbers
// from 2 to r with respect to m
// here m = 1000000007
for
(
int
i = 2; i <= r; i++) {
inv[i] = m - (m / i) * inv[m % i] % m;
}
int
ans = 1;
// for 1/(r!) part
for
(
int
i = 2; i <= r; i++) {
ans = ((ans % m) * (inv[i] % m)) % m;
}
// for (n)*(n-1)*(n-2)*...*(n-r+1) part
for
(
int
i = n; i >= (n - r + 1); i--) {
ans = ((ans % m) * (i % m)) % m;
}
return
ans;
}
/* Driver code*/
int
main()
{
int
n = 5, r = 2;
cout <<
"Value of C("
<< n <<
", "
<< r <<
") is "
<< binomialCoeff(n, r) << endl;
return
0;
}
Java
// JAVA program for the above approach
import
java.util.*;
class
GFG
{
// Function to find binomial
// coefficient
static
int
binomialCoeff(
int
n,
int
r)
{
if
(r > n)
return
0
;
long
m =
1000000007
;
long
inv[] =
new
long
[r +
1
];
inv[
0
] =
1
;
if
(r+
1
>=
2
)
inv[
1
] =
1
;
// Getting the modular inversion
// for all the numbers
// from 2 to r with respect to m
// here m = 1000000007
for
(
int
i =
2
; i <= r; i++) {
inv[i] = m - (m / i) * inv[(
int
) (m % i)] % m;
}
int
ans =
1
;
// for 1/(r!) part
for
(
int
i =
2
; i <= r; i++) {
ans = (
int
) (((ans % m) * (inv[i] % m)) % m);
}
// for (n)*(n-1)*(n-2)*...*(n-r+1) part
for
(
int
i = n; i >= (n - r +
1
); i--) {
ans = (
int
) (((ans % m) * (i % m)) % m);
}
return
ans;
}
/* Driver code*/
public
static
void
main(String[] args)
{
int
n =
5
, r =
2
;
System.out.print(
"Value of C("
+ n+
", "
+ r+
") is "
+binomialCoeff(n, r) +
"\n"
);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program for the above approach
# Function to find binomial
# coefficient
def
binomialCoeff(n, r):
if
(r > n):
return
0
m
=
1000000007
inv
=
[
0
for
i
in
range
(r
+
1
)]
inv[
0
]
=
1
;
if
(r
+
1
>
=
2
)
inv[
1
]
=
1
;
# Getting the modular inversion
# for all the numbers
# from 2 to r with respect to m
# here m = 1000000007
for
i
in
range
(
2
, r
+
1
):
inv[i]
=
m
-
(m
/
/
i)
*
inv[m
%
i]
%
m
ans
=
1
# for 1/(r!) part
for
i
in
range
(
2
, r
+
1
):
ans
=
((ans
%
m)
*
(inv[i]
%
m))
%
m
# for (n)*(n-1)*(n-2)*...*(n-r+1) part
for
i
in
range
(n, n
-
r,
-
1
):
ans
=
((ans
%
m)
*
(i
%
m))
%
m
return
ans
# Driver code
n
=
5
r
=
2
(
"Value of C("
,n ,
", "
, r ,
") is "
,binomialCoeff(n, r))
# This code is contributed by rohan07
C#
// C# program for the above approach
using
System;
public
class
GFG
{
// Function to find binomial
// coefficient
static
int
binomialCoeff(
int
n,
int
r)
{
if
(r > n)
return
0;
long
m = 1000000007;
long
[]inv =
new
long
[r + 1];
inv[0] = 1;
if
(r+1>=2)
inv[1] = 1;
// Getting the modular inversion
// for all the numbers
// from 2 to r with respect to m
// here m = 1000000007
for
(
int
i = 2; i <= r; i++) {
inv[i] = m - (m / i) * inv[(
int
) (m % i)] % m;
}
int
ans = 1;
// for 1/(r!) part
for
(
int
i = 2; i <= r; i++) {
ans = (
int
) (((ans % m) * (inv[i] % m)) % m);
}
// for (n)*(n-1)*(n-2)*...*(n-r+1) part
for
(
int
i = n; i >= (n - r + 1); i--) {
ans = (
int
) (((ans % m) * (i % m)) % m);
}
return
ans;
}
/* Driver code*/
public
static
void
Main(String[] args)
{
int
n = 5, r = 2;
Console.Write(
"Value of C("
+ n+
", "
+ r+
") is "
+binomialCoeff(n, r) +
"\n"
);
}
}
// This code is contributed by 29AjayKumar
JavaScript
<script>
// JavaScript Program for the above approach
// Function to find binomial
// coefficient
function
binomialCoeff(n, r) {
if
(r > n)
return
0;
let m = 1000000007;
let inv =
new
Array(r + 1).fill(0);
inv[0] = 1;
if
(r + 1 >= 2)
inv[1] = 1;
// Getting the modular inversion
// for all the numbers
// from 2 to r with respect to m
// here m = 1000000007
for
(let i = 2; i <= r; i++) {
inv[i] = m - Math.floor(m / i) * inv[m % i] % m;
}
let ans = 1;
// for 1/(r!) part
for
(let i = 2; i <= r; i++) {
ans = ((ans % m) * (inv[i] % m)) % m;
}
// for (n)*(n-1)*(n-2)*...*(n-r+1) part
for
(let i = n; i >= (n - r + 1); i--) {
ans = ((ans % m) * (i % m)) % m;
}
return
ans;
}
/* Driver code*/
let n = 5, r = 2;
document.write(
"Value of C("
+ n +
", "
+ r +
") is "
+ binomialCoeff(n, r) +
"<br>"
);
// This code is contributed by Potta Lokesh
</script>
ProducciónValue of C(5, 2) is 10Complejidad temporal: O(n+k)
Espacio Auxiliar: O(k)
Vea esto para Coeficiente binomial eficiente en espacio y tiempo
Referencias:
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coficients.htmhttps://cp-algorithms.com/algebra/module-inverse.html
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