c++ - triangulo - teorema del binomio

Cálculo del coeficiente binomial(nCk) para n & k grandes

Question

Acabo de ver esta pregunta y no tengo idea de cómo resolverla. ¿Me puede proporcionar algoritmos, códigos C ++ o ideas?

Este es un problema muy simple. Dado el valor de N y K, debe indicarnos el valor del coeficiente binomial C (N, K). Puede estar seguro de que K <= N y el valor máximo de N es 1,000,000,000,000,000. Dado que el valor puede ser muy grande, debe calcular el resultado módulo 1009. Entrada

La primera línea de la entrada contiene el número de casos de prueba T, como máximo 1000. Cada una de las siguientes líneas T consta de dos enteros separados por espacios N y K, donde 0 <= K <= N y 1 <= N <= 1,000,000,000,000,000 . Salida

Para cada caso de prueba, imprima en una nueva línea, el valor del coeficiente binomial C (N, K) módulo 1009. Ejemplo

Entrada:
3
3 1
5 2
10 3

Salida:
3
10
120

Answer 1

Código psudo para el cálculo de nCk:

result = 1    
for i=1 to min{K,N-K}:
   result *= N-i+1
   result /= i
return result

Complejidad de tiempo: O (min {K, NK})

El bucle va from i=1 to min{K,NK} lugar de from i=1 to K , y eso está bien porque

C(k,n) = C(k, n-k)

Y puede calcular la cosa aún más eficientemente si usa la función GammaLn.

nCk = exp(GammaLn(n+1)-GammaLn(k+1)-GammaLn(n-k+1))

La función GammaLn es el logaritmo natural de la función Gamma . Sé que hay un algoritmo eficiente para calcular la función GammaLn, pero ese algoritmo no es en absoluto trivial.

Answer 2

El coeficiente binomial es un factorial dividido por otros dos, aunque el k! término en la parte inferior cancela de una manera obvia.

Observe que si 1009, (incluidos los múltiplos de él), aparece más veces en el numerador que en el denominador, entonces la respuesta mod 1009 es 0. No puede aparecer más veces en el denominador que en el numerador (ya que los coeficientes binomiales son enteros) Por lo tanto, los únicos casos en los que tienes que hacer algo son cuando aparece el mismo número de veces en ambos. No olvide contar los múltiplos de (1009) ^ 2 como dos, y así sucesivamente.

Después de eso, creo que solo estás limpiando casos pequeños (lo que significa pequeños números de valores para multiplicar / dividir), aunque no estoy seguro sin algunas pruebas. En el lado positivo, 1009 es primo, por lo que el módulo aritmético 1009 tiene lugar en un campo, lo que significa que después de descartar múltiplos de 1009 desde arriba y desde abajo, puedes hacer el resto de la multiplicación y la división mod 1009 en cualquier orden.

Cuando quedan casos no pequeños, aún implicarán multiplicar juntos las ejecuciones largas de enteros consecutivos. Esto se puede simplificar conociendo 1008! (mod 1009) 1008! (mod 1009) . Es -1 (1008 si lo prefiere), ya que 1 ... 1008 son los elementos p-1 no son cero del campo principal sobre p . Por lo tanto, consisten en 1, -1, y luego (p-3)/2 pares de inversos multiplicativos.

Entonces, por ejemplo, considere el caso de C ((1009 ^ 3), 200).

Imagine que el número de 1009 es igual (no sé si lo son, porque no he codificado una fórmula para averiguarlo), por lo que este es un caso que requiere trabajo.

En la parte superior tenemos 201 ... 1008, que tendremos que calcular o buscar en una tabla precomputada, luego 1009, luego 1010 ... 2017, 2018, 2019 ... 3026, 3027, etc. .. los rangos son todos -1, así que solo necesitamos saber cuántos rangos hay.

Eso deja 1009, 2018, 3027, que una vez que los hayamos cancelado con 1009 desde la parte inferior solo será 1, 2, 3, ... 1008, 1010, ..., más algunos múltiplos de 1009 ^ 2, que de nuevo Cancelaremos y nos dejaremos con enteros consecutivos para multiplicar.

Podemos hacer algo muy similar con la parte inferior para calcular el producto mod 1009 de "1 ... 1009 ^ 3 - 200 con todas las potencias de 1009 divididas". Eso nos deja con una división en un campo privilegiado. IIRC es complicado en principio, pero 1009 es un número lo suficientemente pequeño como para que podamos gestionar 1000 de ellos (el límite superior en el número de casos de prueba).

Por supuesto, con k = 200, hay una enorme superposición que podría cancelarse más directamente. Eso es lo que quise decir con casos pequeños y casos no pequeños: lo he tratado como un caso no pequeño, cuando en realidad podríamos salirse con la suya simplemente con "fuerza bruta" calculando ((1009^3-199) * ... * 1009^3) / 200!

Answer 3

El siguiente código muestra cómo obtener todos los coeficientes binomiales para un tamaño dado ''n''. Podrías modificarlo fácilmente para detenerte en un k dado para determinar nCk. Es computacionalmente muy eficiente, es fácil de codificar y funciona para n y k muy grandes.

binomial_coefficient = 1
output(binomial_coefficient)
col = 0
n = 5

do while col < n
    binomial_coefficient = binomial_coefficient * (n + 1 - (col + 1)) / (col + 1)
    output(binomial_coefficient)
    col = col + 1
loop

La salida de los coeficientes binomiales es por lo tanto:

1
1 *  (5 + 1 - (0 + 1)) / (0 + 1) = 5 
5 *  (5 + 1 - (1 + 1)) / (1 + 1) = 15
15 * (5 + 1 - (2 + 1)) / (2 + 1) = 15 
15 * (5 + 1 - (3 + 1)) / (3 + 1) = 5 
5 *  (5 + 1 - (4 + 1)) / (4 + 1) = 1

Una vez encontré la fórmula en Wikipedia, pero por alguna razón ya no está allí :(

Answer 4

No creo que quieras calcular C (n, k) y luego reducir el mod 1009. El más grande, C (1e15,5e14) requerirá algo como 1e16 bits ~ 1000 terabytes

Además, la ejecución del bucle en la respuesta de snakiles 1e15 veces parece que podría tomar un tiempo. Lo que podrías usar es, si

n = n0 + n1 * p + n2 * p ^ 2 ... + nd * p ^ d

m = m0 + m1 * p + m2 * p ^ 2 ... + md * p ^ d

(donde 0 <= mi, ni <p)

luego C (n, m) = C (n0, m0) * C (n1, m1) * ... * C (nd, nd) mod p

ver, por ejemplo, http://www.cecm.sfu.ca/organics/papers/granville/paper/binomial/html/binomial.html

Una forma sería usar el triángulo de pascal para construir una tabla de todos los C (m, n) para 0 <= m <= n <= 1009.

Answer 5

Tenga en cuenta que 1009 es un primo.

Ahora puedes usar el teorema de Lucas .

Que estados:

Let p be a prime.
If n  = a1a2...ar when written in base p and
if k  = b1b2...br when written in base p

(pad with zeroes if required)

Then

(n choose k) modulo p = (a1 choose b1) * (a2 choose  b2) * ... * (ar choose br) modulo p.

i.e. remainder of n choose k when divided by p is same as the remainder of
the product (a1 choose b1) * .... * (ar choose br) when divided by p.
Note: if bi > ai then ai choose bi is 0.

Por lo tanto, su problema se reduce a encontrar el módulo de producto 1009 en la mayoría de los números de log N / log 1009 (número de dígitos de N en la base 1009) de la forma a elija b donde a <= 1009 y b <= 1009.

Esto debería facilitarlo incluso cuando N está cerca de 10 ^ 15.

Nota:

Para N = 10 ^ 15, N elige N / 2 es más de 2 ^ (100000000000000), que es mucho más que un largo sin firmar.

Además, el algoritmo sugerido por el teorema de Lucas es O (log N), que es exponentially más rápido que intentar calcular el coeficiente binomial directamente (incluso si hizo un mod 1009 para solucionar el problema de desbordamiento).

Aquí hay un código para Binomial que escribí hace mucho tiempo, todo lo que necesita hacer es modificarlo para realizar las operaciones módulo 1009 (puede haber errores y no necesariamente se recomienda el estilo de codificación):

class Binomial
{
public:
    Binomial(int Max)
    {
        max = Max+1;
        table = new unsigned int * [max]();
        for (int i=0; i < max; i++)
        {
            table[i] = new unsigned int[max]();

            for (int j = 0; j < max; j++)
            {
                table[i][j] = 0;
            }
        }
    }

    ~Binomial()
    {
        for (int i =0; i < max; i++)
        {
            delete table[i];
        }
        delete table;
    }

    unsigned int Choose(unsigned int n, unsigned int k);

private:
    bool Contains(unsigned int n, unsigned int k);

    int max;
    unsigned int **table;
};

unsigned int Binomial::Choose(unsigned int n, unsigned int k)
{
    if (n < k) return 0;
    if (k == 0 || n==1 ) return 1;
    if (n==2 && k==1) return 2;
    if (n==2 && k==2) return 1;
    if (n==k) return 1;


    if (Contains(n,k))
    {
        return table[n][k];
    }
    table[n][k] = Choose(n-1,k) + Choose(n-1,k-1);
    return table[n][k];
}

bool Binomial::Contains(unsigned int n, unsigned int k)
{
    if (table[n][k] == 0) 
    {
        return false;
    }
    return true;
}