nCr con factoriales precalculados

Muchos problemas preguntan de cuántas formas se pueden elegir r elementos de n, lo que se escribe nCr. En los concursos, este conteo se solicita bajo un módulo primo. 🧮

La fórmula clásica es nCr igual a n factorial dividido entre r factorial por n menos r factorial. El problema es que la división se realiza bajo un módulo.

Un solo factorial crece de forma astronómica, así que debe tomar cada uno módulo p. Esto mantiene pequeños todos los valores y conserva la exactitud de la fórmula bajo el módulo.

Construya una matriz fact una sola vez hasta el n máximo que necesite. Cada entrada es la anterior multiplicada por el índice, tomando el módulo p durante el proceso.

La fórmula divide entre dos factoriales, por lo que necesita sus inversos modulares. Recuerde que el inverso convierte la división en una multiplicación sencilla.

Calcule una sola vez el inverso del factorial más grande mediante Fermat, usando pow con el exponente p menos 2. Esa única llamada inicia el resto del proceso.

Obtenga los demás factoriales inversos en un solo recorrido hacia atrás, cada uno a partir del siguiente multiplicado por el índice. No necesita llamadas adicionales a pow.

Ahora nCr es simplemente fact[n] multiplicado por inv_fact[r] y por inv_fact[n menos r], todo módulo p. Son tres accesos y dos multiplicaciones por consulta.

Después del precálculo, cada respuesta de combinación cuesta O(1). Por eso este patrón resulta tan útil cuando un problema solicita miles de valores nCr.

Si r es negativo o mayor que n, la respuesta es 0. Compruebe primero ese límite para no acceder nunca fuera de sus matrices de factoriales.

Establezca el tamaño de la matriz en el n máximo de todas las consultas más un pequeño margen. Un límite demasiado pequeño es una causa habitual de errores de índice.

Después del precálculo, ¿qué velocidad tiene una consulta nCr?

Precalcula los factoriales y sus inversos una sola vez, y después responde cada nCr en O(1) con tres accesos. Controle los límites de r y dimensione las matrices con suficiente capacidad. 🏆