nCr mit vorberechneten Fakultäten
Zählen Sie Kombinationen modulo einer Primzahl
nCr mit vorberechneten Fakultäten ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Kombinationen zählen
Viele Aufgaben fragen, auf wie viele Arten Sie r Elemente aus n auswählen können, geschrieben als nCr. Bei Wettbewerben wird diese Anzahl modulo einer Primzahl verlangt. 🧮
Die Fakultätsformel
Die klassische Formel lautet: nCr ist n Fakultät geteilt durch r Fakultät mal die Fakultät von n minus r. Der Haken ist, dass Division modulo eines Moduls nicht direkt funktioniert.
# nCr = n! / (r! * (n-r)!)Fakultäten wachsen rasant
Eine einzelne Fakultät wächst astronomisch, daher nehmen Sie jede Fakultät modulo p. So bleiben alle Werte klein, während die Formel unter dem Modulus korrekt bleibt.
Alle Fakultäten vorberechnen
Erstellen Sie einmal ein fact-Array bis zum größten benötigten n. Jeder Eintrag ist der vorherige Wert multipliziert mit dem Index, wobei Sie währenddessen modulo p nehmen.
fact[i] = fact[i-1] * i % MODDivision benötigt Inverse
Die Formel dividiert durch zwei Fakultäten, daher benötigen Sie deren modulare Inverse. Denken Sie daran: Das Inverse verwandelt Division in eine einfache Multiplikation.
Die größte Fakultät invertieren
Berechnen Sie das Inverse der größten Fakultät mit Fermat nur einmal, indem Sie pow mit dem Exponenten p minus 2 verwenden. Dieser eine Aufruf bildet die Grundlage für den Rest.
inv_fact[n] = pow(fact[n], MOD - 2, MOD)Inverse rückwärts berechnen
Ermitteln Sie die übrigen inversen Fakultäten in einem einzigen Rückwärtsdurchlauf, jeweils aus dem nächsten Wert multipliziert mit dem Index. Zusätzliche pow-Aufrufe sind nicht nötig.
inv_fact[i] = inv_fact[i+1] * (i+1) % MODnCr zusammensetzen
Jetzt ist nCr einfach fact[n] mal inv_fact[r] mal inv_fact[n minus r], alles modulo p. Pro Abfrage benötigen Sie drei Zugriffe und zwei Multiplikationen.
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MODJede Abfrage ist sofort erledigt
Nach der Vorberechnung ist jede Kombination in O(1) beantwortet. Deshalb ist dieses Muster besonders nützlich, wenn eine Aufgabe Tausende nCr-Werte verlangt.
Sonderfälle behandeln
Wenn r negativ oder größer als n ist, lautet die Antwort 0. Prüfen Sie diese Bedingung zuerst, damit Sie nie außerhalb Ihrer Fakultäts-Arrays zugreifen.
if r < 0 or r > n: return 0Arrays großzügig dimensionieren
Setzen Sie die Arraygröße auf das größte n aller Abfragen plus einen kleinen Puffer. Ein zu kleines limit ist hier eine häufige Ursache für Indexfehler.
N = 200005Schnelltest
Wie schnell ist eine einzelne nCr-Abfrage nach der Vorberechnung?
Rückblick
Sie berechnen Fakultäten und ihre Inversen einmal vor und beantworten danach jedes nCr mit O(1) und drei Zugriffen. Prüfen Sie die Grenzen von r und dimensionieren Sie die Arrays ausreichend groß. 🏆
Häufig gestellte Fragen
Ist die Lektion „nCr mit vorberechneten Fakultäten“ kostenlos?
Ja — der vollständige Text von „nCr mit vorberechneten Fakultäten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „nCr mit vorberechneten Fakultäten“?
Zählen Sie Kombinationen modulo einer Primzahl Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „nCr mit vorberechneten Fakultäten“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Rechnen modulo einer Primzahl
- Schnelle modulare Exponentiation
- Modulares Inverses mit Fermat
- nCr mit vorberechneten Fakultäten