nCr med förberäknade fakulteter
Räkna kombinationer modulo ett primtal
nCr med förberäknade fakulteter är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Räkna kombinationer
Många problem frågar hur många sätt man kan välja r objekt bland n, vilket skrivs nCr. I tävlingsuppgifter vill man beräkna antalet modulo ett primtal. 🧮
Fakultetsformeln
Den klassiska formeln är nCr lika med n fakultet dividerat med r fakultet gånger (n minus r) fakultet. Haken är att division med en modul inte fungerar direkt.
# nCr = n! / (r! * (n-r)!)Fakulteter växer explosionsartat
En enda fakultet växer astronomiskt, så Du tar modulo p för varje fakultet. Då hålls alla värden små samtidigt som formeln förblir exakt modulo modulen.
Förberäkna alla fakulteter
Bygg en fact-array en gång, upp till det största n Du behöver. Varje element är det föregående elementet multiplicerat med indexet, med modulo p under beräkningen.
fact[i] = fact[i-1] * i % MODDivision kräver inverser
Formeln dividerar med två fakulteter, så Du behöver deras modulära inverser. Kom ihåg att inversen omvandlar division till en enkel multiplikation.
Invertera den största fakulteten
Beräkna inversen till den största fakulteten en enda gång med Fermat, genom att använda pow med exponenten p minus 2. Det enda anropet blir startpunkten för resten.
inv_fact[n] = pow(fact[n], MOD - 2, MOD)Beräkna inverserna baklänges
Beräkna de övriga inversa fakulteterna i en enda genomgång baklänges, var och en från nästa värde multiplicerat med indexet. Inga extra anrop till pow behövs.
inv_fact[i] = inv_fact[i+1] * (i+1) % MODSätt ihop nCr
Nu är nCr bara fact[n] multiplicerat med inv_fact[r] och inv_fact[n minus r], allt modulo p. Tre uppslag och två multiplikationer per fråga.
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MODVarje fråga besvaras direkt
Efter förberäkningen tar varje kombinationssvar O(1). Därför är mönstret så användbart när ett problem ber om tusentals nCr-värden.
Hantera specialfallen
Om r är negativt eller större än n är svaret 0. Kontrollera den gränsen först, så att Du aldrig indexerar utanför fakultetsarrayerna.
if r < 0 or r > n: return 0Välj generösa arraystorlekar
Sätt arraystorleken till det största n bland alla frågor, plus lite marginal. En för liten limit är en vanlig orsak till indexfel här.
N = 200005Snabb kontroll
Hur snabbt går en nCr-fråga efter förberäkningen?
Sammanfattning
Du förberäknar fakulteter och deras inverser en gång och besvarar sedan varje nCr på O(1) med tre uppslag. Kontrollera r:s gränser och gör arrayerna tillräckligt stora. 🏆
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”nCr med förberäknade fakulteter” gratis?
Ja – hela texten till ”nCr med förberäknade fakulteter” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”nCr med förberäknade fakulteter”?
Räkna kombinationer modulo ett primtal Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”nCr med förberäknade fakulteter”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Arbeta modulo ett primtal
- Snabb modulär exponentiering
- Modulär invers via Fermat
- nCr med förberäknade fakulteter