¿Cómo podemos computadoras (N choose K)% M en C o C++ sin invocar desbordamiento?¿Cómo podemos calcular N elegir K módulo un número primo sin desbordamiento?
Para el caso particular cuando N (4 < = N < = 1,000) y K (1 < = K < = N) y M = 1.000.003.
Para calcular (n elegir k)% M, puede calcular por separado el modulador (n!) Módulo M y el denominador (k! * (N - k)!) Módulo M y luego multiplicar el nominador por el denominador modular multiplicativo inverso (en M). Como M es primo, puede usar el pequeño teorema de Fermat para calcular el inverso multiplicativo.
Hay una buena explicación, con el código de ejemplo, en el siguiente enlace (problema SuperSum):
Para obtener una velocidad adicional, calcule el numerador como el producto de (K + 1) a N y el denominador como K !. Sabemos que no habrá ningún factor de M en el cálculo, porque es primo y mayor que N. Por lo tanto, podemos cancelar arriba y abajo sin preocuparnos de que lo que estamos cancelando podría ser un múltiplo de M (es decir, 0). –
Exactamente aprendí de lo mismo. – Quixotic
Pero ahora veo que 1,000,000,003 no es primordial, ¿alguna idea de cómo resolver esto ahora? – Quixotic
podría utilizar la fórmula recursiva desde el enlace que diste y hacer el cálculo mod M.
Uso Stirling's approximation para calcular el coeficiente binomial. Luego solo calcula el módulo como de costumbre.
¿Cómo ayuda una aproximación calcular el coeficiente binomial módulo M? Las aproximaciones son bastante sin sentido en la aritmética de módulo. –
Lo siento, me perdí la parte de aproximación. – Quixotic
Aquí está un ejemplo sencillo:
(A * B * C) % N ... is equal to... ((A % N) * (B % N) * (C % N)) % N;
Es decir, todo lo que necesita para aplicar a cada módulo operando y el producto, o tan pronto como llega a ser grande un número. Y por último, el módulo debe aplicarse al resultado global.
Con 32 bit int aún puede causar un desbordamiento en 1000000000 * 1000. – ybungalobill
@ ybungalobill: aplicar '((1000000000% N) * (1000)% N)% N'. – Nawaz
tenga en cuenta que el módulo es M en la pregunta, no N, y el ejemplo dado, mientras que en realidad no es primo, es de aproximadamente mil millones. Entonces '1000000000% N' sigue siendo' 1000000000'. Para evitar el desbordamiento, necesitaría un tipo entero tan grande como N^2 (por ejemplo, 'long long' o' int64_t', si está disponible) –
Desde 1000000003 = 23 * 307 * 141623 se puede calcular (n Choses k) mod 23 , 307 y 141623 y luego aplicar el teorema del recordatorio chino [1]. Al calcular n !, k! y (n-k)!, debe calcular todo el mod 23, 307 y 141623 en cada paso para evitar el desbordamiento.
De esta manera, debe evitar el desbordamiento incluso en máquinas de 32 bits.
Una pequeña mejora sería calcular (n choses k) mod 141623 y 7061 (23 * 307) (editar: pero puede ser un poco complicado calcular el módulo inverso 7061, así que no haría esto)
Lo siento por mi pobre inglés.
[1] http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Edit2: Otro potencial problema que he encontrado es la hora de calcular n! mod 23 (por ejemplo) probablemente será 0, pero eso no implica que (n elige k) es 0 mod 23, por lo que debe contar cuántas veces 23 divide n! (n-k)! yk! antes de calcular (n elige k). Calcular esto es fácil, p divide n! exactamente piso (n/p) + piso (n/p²) + ... veces. ¡Si sucede que 23 divide n! las mismas veces que divide k! y (nk)!, usted procede a calcular (n elige k) mod 23 dividiendo por 23 cada multiplicador cada vez. Lo mismo aplica para 307, pero no para 141623
Para los primos pequeños, 23 y 307, puede usar http://en.wikipedia.org/wiki/Lucas%27_theorem en lugar de contar poderes. –
Parece que ya lo han [respondido en otro lugar] (http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690) –