nCr med forhåndsberegnede fakulteter
Tell kombinasjoner modulo et primtall
nCr med forhåndsberegnede fakulteter er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Tell kombinasjoner
Mange oppgaver spør hvor mange måter du kan velge r elementer fra n på, skrevet nCr. I konkurranser skal dette antallet beregnes modulo en primtallsmodul. 🧮
Fakultetsformelen
Den klassiske formelen er at nCr er n-fakultet delt på produktet av r-fakultet og (n − r)-fakultet. Utfordringen er at divisjon modulo en modul.
# nCr = n! / (r! * (n-r)!)Fakulteter vokser enormt
Ett enkelt fakultet vokser astronomisk, så du tar modulo p for hvert av dem. Da holder alle verdiene seg små, samtidig som formelen forblir nøyaktig modulo modulen.
Forhåndsberegn alle fakulteter
Bygg en fact-tabell én gang, opp til den største n-verdien du trenger. Hver oppføring er den forrige oppføringen multiplisert med indeksen, redusert modulo p underveis.
fact[i] = fact[i-1] * i % MODDivisjon krever inverser
Formelen dividerer med to fakulteter, så du trenger deres modulære inverser. Husk at inversen gjør divisjon om til en enkel multiplikasjon.
Finn inversen til det største fakultetet
Beregn inversen til det største fakultetet bare én gang med Fermat, ved å bruke pow med eksponenten p − 2. Dette ene kallet legger grunnlaget for resten.
inv_fact[n] = pow(fact[n], MOD - 2, MOD)Beregn inversene baklengs
Finn de andre inversene til fakultetene i ett baklengs gjennomløp, hver beregnet fra den neste multiplisert med indeksen. Du trenger ingen ekstra kall til pow.
inv_fact[i] = inv_fact[i+1] * (i+1) % MODSett sammen nCr
Nå er nCr ganske enkelt fact[n] multiplisert med inv_fact[r] og inv_fact[n − r], alt modulo p. Det blir tre oppslag og to multiplikasjoner per spørring.
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MODHver spørring tar konstant tid
Etter forhåndsberegningen tar hvert kombinasjonssvar O(1)-tid. Derfor er denne metoden så nyttig når en oppgave ber om tusenvis av nCr-verdier.
Håndter randtilfellene
Hvis r er negativ eller større enn n, er svaret 0. Sjekk denne grensen først, slik at du aldri bruker en indeks utenfor fakultetstabellene.
if r < 0 or r > n: return 0Gi arrayene god størrelse
Sett størrelsen på arrayene til den største n-verdien blant alle spørringene, pluss litt ekstra. En for liten limit er en vanlig årsak til indeksfeil her.
N = 200005Rask sjekk
Hvor rask er én nCr-spørring etter forhåndsberegningen?
Oppsummering
Du forhåndsberegner fakulteter og inversene deres én gang, og svarer deretter på hver nCr-spørring på O(1)-tid med tre oppslag. Kontroller grensene for r og bruk store nok arrayer. 🏆
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «nCr med forhåndsberegnede fakulteter» gratis?
Ja – hele teksten i «nCr med forhåndsberegnede fakulteter» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «nCr med forhåndsberegnede fakulteter»?
Tell kombinasjoner modulo et primtall Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «nCr med forhåndsberegnede fakulteter»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Regn modulo et primtall
- Rask modulær eksponentiering
- Modulær invers ved hjelp av Fermat
- nCr med forhåndsberegnede fakulteter