algorithm - Necesita ayuda en las preguntas de mod 1000000007
math language-agnostic (3)
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.
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 ++.
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
}
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.