Hallar el coeficiente binomial para n y k grandes módulo m

Deseamos brindarte la mejor información que hallamos en línea. Esperamos que te resulte de ayuda y si quieres comentarnos alguna mejora puedes hacerlo..

El coeficiente binominal de (n, k) se calcula por la fórmula:

(n, k) = n! / k! / (n - k)!

Para que esto funcione para grandes cantidades n y k módulo m observa eso:

1. Módulo factorial de un número m se puede calcular paso a paso, en cada paso tomando el resultado % m. Sin embargo, esto será demasiado lento con n hasta 10^18. Entonces, hay métodos más rápidos donde la complejidad está limitada por el módulo, y puedes usar algunos de ellos.

2. La división (a / b) mod m es igual a (a * b^-1) mod m, donde b^-1 es el inverso de b módulo m (es decir, (b * b^-1 = 1) mod m).

Esto significa que:

(n, k) mod m = (n! * (k!)^-1 * ((n - k)!)^-1) mod m

El inverso de un número se puede encontrar de manera eficiente utilizando el algoritmo euclidiano extendido. Suponiendo que haya resuelto el cálculo factorial, el resto del algoritmo es sencillo, solo tenga cuidado con los desbordamientos de enteros en la multiplicación. Aquí hay un código de referencia que funciona hasta n=10^9. Para manejar números más grandes, el cálculo factorial debe reemplazarse con un algoritmo más eficiente y el código debe adaptarse ligeramente para evitar desbordamientos de enteros, pero la idea principal seguirá siendo la misma:

#define MOD 1000000007

// Extended Euclidean algorithm
int xGCD(int a, int b, int &x, int &y) 
    if (b == 0) 
        x = 1;
        y = 0;
        return a;
    

    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (long long)(a / b) * y1;
    return gcd;


// factorial of n modulo MOD
int modfact(int n) 
    int result = 1;
    while (n > 1) 
        result = (long long)result * n % MOD;
        n -= 1;
    
    return result;


// multiply a and b modulo MOD
int modmult(int a, int b) 
    return (long long)a * b % MOD;


// inverse of a modulo MOD
int inverse(int a) 
    int x, y;
    xGCD(a, MOD, x, y);
    return x;


// binomial coefficient nCk modulo MOD
int bc(int n, int k)

    return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k)));

En primer lugar, no es necesario precalcular ni almacenar todos los valores posibles de aCb. se pueden calcular por caso.

En segundo lugar, para el caso especial cuando (k < m) y (n < m^2), el teorema de Lucas se reduce fácilmente al siguiente resultado:

(n elige k) mod m = ((n mod m) elige k) mod m

luego, dado que (n mod m) <10^9+7, simplemente puede usar el código propuesto por @kfx.

Solo usa el hecho de que

(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

entonces en realidad solo tienes 2*k=2*10^5 factores Para el inverso de un número puedes usar la sugerencia de kfx desde tu m es primo

---

---

Utiliza Nuestro Buscador