nCr con fattoriali precalcolati

Molti problemi chiedono in quanti modi sia possibile scegliere r elementi tra n, indicato con nCr. Nelle gare, questo conteggio va eseguito con un modulo primo. 🧮

La formula classica è nCr uguale a n fattoriale diviso il prodotto di r fattoriale e (n meno r) fattoriale. Il problema è che la divisione non funziona direttamente con un modulo.

Un singolo fattoriale cresce a dismisura, quindi si applica il modulo p a ciascuno di essi. In questo modo ogni valore resta piccolo, mentre la formula rimane esatta con il modulo.

Crei una volta sola un array fact fino al valore massimo di n necessario. Ogni elemento è il precedente moltiplicato per l'indice, con il modulo p applicato man mano.

La formula divide per due fattoriali, quindi servono i loro inversi modulari. Ricordi che l'inverso trasforma la divisione in una semplice moltiplicazione.

Calcoli una sola volta l'inverso del fattoriale massimo con Fermat, usando pow con esponente p meno 2. Questa singola chiamata fornisce il punto di partenza per tutti gli altri.

Ottenga gli altri inversi dei fattoriali con un unico passaggio all'indietro, ricavando ciascuno dal successivo moltiplicato per l'indice. Non servono altre chiamate a pow.

Ora nCr è semplicemente fact[n] moltiplicato per inv_fact[r] e per inv_fact[n minus r], tutto modulo p. Tre accessi e due moltiplicazioni per ogni query.

Dopo il precalcolo, ogni risposta alle combinazioni richiede O(1). Ecco perché questo schema è ideale quando un problema richiede migliaia di valori nCr.

Se r è negativo o maggiore di n, la risposta è 0. Controlli prima questo limite, così non accederà mai a una posizione fuori dagli array dei fattoriali.

Imposti la dimensione dell'array sul valore massimo di n tra tutte le query, aggiungendo un piccolo margine. Un limite troppo piccolo è una causa comune di errori di indice.

Precalcola una volta i fattoriali e i loro inversi, poi risponda a ogni nCr in O(1) con tre accessi. Controlli i limiti di r e dimensioni gli array con sufficiente margine. 🏆