Önceden Hesaplanmış Faktöriyellerle nCr

Birçok problem, n öğe arasından r öğesini seçmenin kaç yolu olduğunu sorar; bu değer nCr ile gösterilir. Yarışmalarda bu sayının asal bir modül altındaki değeri istenir. 🧮

Klasik formüle göre nCr, n faktöriyelinin r faktöriyeli ile n eksi r faktöriyelinin çarpımına bölünmesine eşittir. Sorun, modül altında bölme yapılmasıdır.

Tek bir faktöriyel bile astronomik ölçüde büyür; bu nedenle her birini p'ye göre modülo olarak hesaplayın. Böylece formül modül altında kesinliğini korurken tüm değerler küçük kalır.

İhtiyaç duyduğunuz en büyük n değerine kadar bir faktöriyel dizisini bir kez oluşturun. Her öğe, önceki öğe ile indisinin çarpımının modül altında hesaplanmasıyla elde edilir.

Formülde iki faktöriyene bölme yapıldığından bunların modüler terslerine ihtiyacınız vardır. Ters alma işleminin bölmeyi doğrudan bir çarpmaya dönüştürdüğünü hatırlayın.

En büyük faktöriyelinin tersini, p eksi 2 üssünü kullanarak Fermat yöntemiyle yalnızca bir kez hesaplayın. Bu tek çağrı geri kalan işlemlerin başlangıç değerini sağlar.

Diğer ters faktöriyelleri tek bir geriye doğru geçişte, her birini sonraki öğe ile indisinin çarpımından elde ederek hesaplayın. Ekstra pow çağrılarına gerek kalmaz.

Artık nCr, fact[n] ile inv_fact[r] ve inv_fact[n minus r] değerlerinin çarpımının p'ye göre modülosudur. Her sorgu için üç dizi erişimi ve iki çarpma yeterlidir.

Ön hesaplamadan sonra her kombinasyon cevabı O(1) sürede bulunur. Bir problem binlerce nCr değeri istediğinde bu yöntem bu yüzden çok etkilidir.

r negatifse veya n'den büyükse cevap 0 olur. Faktöriyel dizilerinizin dışına taşmamak için önce bu sınırı denetleyin.

Dizi boyutunu, tüm sorgulardaki en büyük n değerine küçük bir pay ekleyecek şekilde belirleyin. Çok küçük bir sınır, burada dizin hatalarının yaygın bir nedenidir.

Ön hesaplamadan sonra tek bir nCr sorgusu ne kadar hızlıdır?

Faktöriyelleri ve terslerini bir kez önceden hesaplayıp her nCr sorgusunu üç dizi erişimiyle O(1) sürede yanıtlayabilirsiniz. r sınırlarını denetleyin ve dizileri yeterince büyük oluşturun. 🏆