nCr dengan Faktorial Pra-kiraan

Banyak masalah bertanya berapa banyak cara untuk memilih r item daripada n, ditulis sebagai nCr. Pertandingan memerlukan kiraan itu di bawah modulo nombor perdana. 🧮

Formula klasik ialah nCr bersamaan dengan n faktorial dibahagikan dengan hasil darab r faktorial dan n tolak r faktorial. Masalahnya ialah pembahagian di bawah modulo.

Satu faktorial sahaja boleh membesar secara astronomi, jadi ambil modulo p bagi setiap satunya. Ini memastikan setiap nilai kekal kecil sementara formula tetap tepat di bawah modulo.

Bina tatasusunan fact sekali sehingga n terbesar yang Anda perlukan. Setiap entri ialah entri sebelumnya didarab dengan indeks, dan modulo p diambil sepanjang proses.

Formula itu membahagi dengan dua faktorial, jadi Anda memerlukan invers modulo bagi kedua-duanya. Ingat bahawa invers menukar pembahagian menjadi pendaraban yang mudah.

Kira invers bagi faktorial terbesar sekali sahaja menggunakan Fermat, dengan pow dan eksponen p tolak 2. Satu panggilan itu memulakan baki proses.

Dapatkan invers faktorial yang lain melalui satu laluan songsang, setiap satunya daripada nilai seterusnya didarab dengan indeks. Tiada panggilan pow tambahan diperlukan.

Sekarang nCr hanyalah fact[n] didarab dengan inv_fact[r] dan inv_fact[n tolak r], semuanya modulo p. Tiga carian dan dua pendaraban bagi setiap pertanyaan.

Selepas pengiraan awal, setiap jawapan kombinasi mengambil masa O(1). Itulah sebab corak ini sangat berguna apabila masalah meminta ribuan values nCr.

Jika r negatif atau lebih besar daripada n, jawapannya ialah 0. Periksa had itu dahulu supaya Anda tidak mengakses indeks di luar tatasusunan faktorial.

Tetapkan saiz tatasusunan kepada n maksimum bagi semua pertanyaan, ditambah sedikit ruang. Had yang terlalu kecil ialah punca biasa ralat indeks di sini.

Anda mengira awal faktorial dan inversnya sekali, kemudian menjawab setiap nCr dalam O(1) dengan tiga carian. Pastikan had r diperiksa dan tatasusunan cukup besar. 🏆