algorithm - Necesita ayuda en las preguntas de mod 1000000007

math language-agnostic

Question

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

por ejemplo: (500! / 20!) mod 1000000007

Estoy familiarizado con BigIntegers, pero calcular el módulo después de calcular factorial de 500 (incluso después de usar DP) parece tomar un montón de tiempo.

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

Aquí hay uno de esos problemas que estoy tratando de resolver en este momento: http://www.codechef.com/FEB12/problems/WCOUNT

Realmente sería útil si alguien pudiera dirigirme a un tutorial o un enfoque para manejar estos problemas de codificación. Estoy familiarizado con Java y C ++.

Answer 1

Comience por observar que 500!/20! es el producto de todos los números del 21 al 500, inclusive y Siguiente, observe que puede realizar la multiplicación del módulo elemento por elemento, 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 2

Creo que esto podría ser útil para ti

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
}

Answer 3

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 necesita reducir el módulo en cada paso. Solo hazlo con la frecuencia suficiente para evitar que el número se vuelva demasiado grande.

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