Necesito ayuda en las preguntas de mod 1000000007

Question

Soy débil en matemáticas y siempre me quedo atascado con los problemas que requieren módulo de respuesta.

por ejemplo: (! 500/20) mod 1000000007

estoy familiarizado con BigIntegers pero el cálculo de módulo después de calcular factorial de 500 (incluso después de usar DP) parece tener una carga de tiempo.

Me gustaría saber si hay una forma particular de abordar/tratar este tipo de problemas.

Aquí es uno de esos problemas que estoy tratando de resolver en la actualidad http://www.codechef.com/FEB12/problems/WCOUNT

Sería realmente útil si alguien podría dirigir a un tutorial o un enfoque para manejar estos problemas de codificación. Estoy familiarizado con Java y C++.

Answer 1

La clave para estas tareas de módulo de gran número no es calcular el resultado completo antes de realizar el módulo. Debe reducir el módulo en los pasos intermedios para mantener el número pequeño:

500!/20! = 21 * 22 * 23 * ... * 500 

21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200 

4475671200 mod 1000000007 = 475671172 
475671172 * 28 mod 1000000007 = 318792725 
318792725 * 29 mod 1000000007 = 244988962 
244988962 * 30 mod 1000000007 = 349668811 

... 

31768431 * 500 mod 1000000007 = 884215395 

500!/20! mod 1000000007 = 884215395 

No es necesario para reducir el módulo a cada paso. Solo hazlo con la frecuencia suficiente para evitar que el número se vuelva demasiado grande.

---

Nota que el valor máximo de long es 2^63 - 1. Por lo tanto la realización de 64 multiplicaciones de bits entre dos valores enteros positivos (es decir, uno de los operandos es un long) no se desbordará long. Puede realizar de forma segura el resto de la operación % después (si eso también es positivo) y volver a un número entero cuando sea necesario.

Answer 2

Comience observando que 500!/20! es el producto de todos los números del 21 al 500, inclusive y siguiente, observe que puede realizar multiplicación de módulo artículo por artículo, tomando %1000000007 al final de cada operación. Debería poder escribir su programa ahora. Tenga cuidado de no desbordar el número: 32 bits pueden no ser suficientes.

Answer 3

Creo que esto podría ser de alguna utilidad para usted

for(mod=prime,res=1,i=20;i<501;i++) 
{ 
res*=i; // an obvious step to be done 
if(res>mod) // check if the number exceeds mod 
res%=mod; // so as to avoid the modulo as it is costly operation 
}