Gracias por A2A.
¡Existen múltiples formas de evaluar nCr mod mo n! mod m.
La forma más común de evaluar n! mod m es tomar un módulo después de cada paso de multiplicación mientras se evalúa n !. P.ej. ¡Para calcular 1000! mod m, se puede usar un bucle simple para evaluarlo como
(…. ((((1 mod m) * 2) mod m) * 3) mod m….) * 1000) mod m.
Obviamente n! mod m = 0 para n> = m.
Para calcular nCr mod m,
uno necesita saber cómo evaluar (a / b) mod m.
Si bym son coprimos entre sí (en general, m recibe un número primo),
(a / b) mod m = (a mod m) * (b invmod m) = (a mod m) * (b ^ (m-2) mod m). Aquí, invmod es el módulo inverso. Existen muchos foros de intercambio de pila descendente y páginas wiki desde donde puede leer sobre el módulo inverso y la derivación de los resultados anteriores.
Sin embargo, el método de elevar a la potencia (m-2) es válido solo cuando el denominador de la fracción, es decir, bym son coprimos. En caso de que no lo sean, existen otros métodos complejos que involucran la función Totient que puede googlear.
Ahora,
nCr mod m = n! / r! (nr)! mod m
= (n! mod m) * (((r! mod m * (nr)! mod m) ^ (m-2)) mod m).
Uno puede usar exponenciación modular para evaluar (a ^ b) mod m, que supongo que ya sabe. (En caso de que no lea un tutorial popular de topcoder sobre exponenciación modular.
- ¿Los investigadores que elaboran algoritmos útiles ganan mucho dinero cuando sus algoritmos se aplican ampliamente en la industria?
- ¿Cómo recomienda Foursquare las sugerencias de mis amigos de Facebook?
- Cómo desarrollar un algoritmo para detectar rangos de negociación horizontales / patrones de consolidación
- Cómo mejorar en algoritmos, estructuras de datos y programación competitiva, solo por puro aprendizaje, así como por ubicaciones en empresas de primer nivel, en un año
- Si la compresión sin pérdida es completamente reversible, ¿por qué no omitimos un paso y solo usamos los archivos en su estado comprimido?
Espero haberte dado una idea aproximada de cómo se debe hacer y qué se debe leer para evaluarlos.
