nCr z wcześniej obliczonymi silniami

Wiele zadań pyta, na ile sposobów można wybrać r elementów spośród n, co zapisuje się jako nCr. W zadaniach konkursowych wynik należy obliczyć modulo liczby pierwszej. 🧮

Klasyczny wzór mówi, że nCr jest równe n silnia podzielone przez iloczyn r silnia oraz n minus r silnia. Problem polega na tym, że jest to dzielenie modulo.

Pojedyncza silnia rośnie astronomicznie, dlatego każdą z nich należy obliczać modulo p. Utrzymuje to każdą wartość w małym zakresie, a wzór pozostaje dokładny modulo.

Zbuduj raz tablicę fact aż do największej potrzebnej wartości n. Każdy element jest równy poprzedniemu pomnożonemu przez indeks, z redukcją modulo p na bieżąco.

Wzór dzieli przez dwie silnie, więc potrzebne są ich odwrotności modularne. Należy pamiętać, że odwrotność zamienia dzielenie w zwykłe mnożenie.

Oblicz odwrotność największej silni tylko raz za pomocą Fermata, używając pow z wykładnikiem p minus 2. To pojedyncze wywołanie inicjuje pozostałe wartości.

Pozostałe odwrotności silni uzyskaj w jednym przejściu od końca, każdą na podstawie następnej wartości pomnożonej przez indeks. Nie są potrzebne dodatkowe wywołania pow.

Teraz nCr to po prostu fact[n] pomnożone przez inv_fact[r] oraz inv_fact[n minus r], wszystko modulo p. Na każde zapytanie przypadają trzy odczyty i dwa mnożenia.

Po wstępnym obliczeniu odpowiedź na każdą kombinację uzyskuje się w czasie O(1). Dlatego ten schemat świetnie sprawdza się, gdy zadanie wymaga tysięcy wartości nCr.

Jeśli r jest ujemne albo większe od n, odpowiedzią jest 0. Najpierw sprawdź ten warunek, aby nigdy nie odwołać się poza zakres tablic z silniami.

Ustaw rozmiar tablicy na maksymalną wartość n ze wszystkich zapytań i dodaj niewielki zapas. Zbyt mały limit często powoduje tu błędy indeksowania.

Można raz wstępnie obliczyć silnie i ich odwrotności, a następnie odpowiadać na każde zapytanie nCr w czasie O(1), wykonując trzy odczyty. Należy sprawdzać zakres r i tworzyć wystarczająco duże tablice. 🏆