nCr avec des factorielles précalculées

De nombreux problèmes demandent combien de façons il existe de choisir r éléments parmi n, ce qui s’écrit nCr. Les concours demandent ce nombre avec un modulo premier. 🧮

La formule classique est nCr égal à n factorielle divisé par r factorielle multiplié par n moins r factorielle. Le problème vient de la division avec un modulo.

Une seule factorielle augmente de façon astronomique : prenez donc chacune modulo p. Chaque valeur reste ainsi petite, tandis que la formule demeure exacte avec ce modulo.

Construisez une fois un tableau de factorielles jusqu’au plus grand n dont vous avez besoin. Chaque élément est le précédent multiplié par l’indice, puis réduit modulo p.

La formule divise par deux factorielles : vous avez donc besoin de leurs inverses modulaires. Souvenez-vous que l’inverse transforme la division en une multiplication simple.

Calculez une seule fois l’inverse de la plus grande factorielle avec Fermat, en utilisant pow avec l’exposant p - 2. Cet unique appel permet d’obtenir tous les autres.

Obtenez les autres inverses de factorielles en un seul passage vers l’arrière, chacun à partir du suivant multiplié par l’indice. Aucun appel supplémentaire à pow n’est nécessaire.

À présent, nCr est simplement fact[n] multiplié par inv_fact[r], puis par inv_fact[n moins r], le tout modulo p. Trois accès et deux multiplications par requête.

Après le précalcul, chaque réponse de combinaison s’obtient en O(1). C’est pourquoi cette méthode est idéale lorsqu’un problème demande des milliers de valeurs nCr.

Si r est négatif ou supérieur à n, la réponse vaut 0. Vérifiez d’abord cette condition afin de ne jamais accéder à un indice en dehors de vos tableaux de factorielles.

Définissez la taille de votre tableau comme le n maximal de toutes les requêtes, avec une petite marge. Une limite trop petite provoque souvent des erreurs d’indice ici.

Après le précalcul, quelle est la vitesse d’une requête nCr ?

Vous précalculez une fois les factorielles et leurs inverses, puis répondez à chaque requête nCr en O(1) avec trois accès. Vérifiez les limites de r et prévoyez des tableaux assez grands. 🏆