nCr dengan Faktorial yang Telah Dihitung
Menghitung kombinasi modulo bilangan prima
nCr dengan Faktorial yang Telah Dihitung adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Menghitung Kombinasi
Banyak soal menanyakan berapa banyak cara untuk memilih r item dari n, yang ditulis sebagai nCr. Dalam kompetisi, jumlah tersebut biasanya diminta menggunakan modulus prima. 🧮
Rumus Faktorial
Rumus klasiknya adalah nCr sama dengan faktorial n dibagi faktorial r dikali faktorial n dikurangi r. Masalahnya adalah pembagian menggunakan modulo.
# nCr = n! / (r! * (n-r)!)Faktorial Membesar dengan Cepat
Satu faktorial saja dapat membesar secara astronomis, jadi ambil modulo p untuk setiap faktorial. Dengan begitu, setiap nilai tetap kecil sementara rumusnya tetap tepat dalam modulus tersebut.
Lakukan Praperhitungan Semua Faktorial
Buat larik faktorial sekali hingga n terbesar yang Anda perlukan. Setiap entri adalah entri sebelumnya dikalikan indeksnya, lalu diambil modulo p.
fact[i] = fact[i-1] * i % MODPembagian Memerlukan Invers
Rumus tersebut membagi dengan dua faktorial, jadi Anda memerlukan invers modulo keduanya. Ingat, invers mengubah pembagian menjadi perkalian yang sederhana.
Cari Invers Faktorial Teratas
Hitung invers dari faktorial terbesar sekali saja dengan Fermat, menggunakan pow dengan eksponen p dikurangi 2. Satu pemanggilan itu menjadi dasar untuk sisanya.
inv_fact[n] = pow(fact[n], MOD - 2, MOD)Hitung Mundur Invers
Dapatkan invers faktorial lainnya dalam satu lintasan mundur, masing-masing dari entri berikutnya dikalikan indeksnya. Tidak diperlukan pemanggilan pow tambahan.
inv_fact[i] = inv_fact[i+1] * (i+1) % MODSusun nCr
Sekarang nCr cukup dihitung sebagai fact[n] dikali inv_fact[r] dikali inv_fact[n dikurangi r], semuanya modulo p. Setiap kueri hanya memerlukan tiga akses dan dua perkalian.
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MODSetiap Kueri Berlangsung Seketika
Setelah praperhitungan, jawaban setiap kombinasi memiliki kompleksitas O(1). Itulah sebabnya pola ini sangat berguna saat soal meminta ribuan nilai nCr.
Tangani Kasus Tepi
Jika r negatif atau lebih besar daripada n, jawabannya adalah 0. Periksa batas tersebut terlebih dahulu agar Anda tidak pernah mengakses indeks di luar larik faktorial.
if r < 0 or r > n: return 0Sediakan Ukuran Larik yang Cukup Besar
Tetapkan ukuran larik berdasarkan n maksimum dari semua kueri, lalu tambahkan sedikit ruang. Batas yang terlalu kecil adalah penyebab umum kesalahan indeks di sini.
N = 200005Pemeriksaan Cepat
Setelah praperhitungan, seberapa cepat satu kueri nCr?
Ringkasan
Anda melakukan praperhitungan faktorial dan inversnya sekali, lalu menjawab setiap nCr dalam O(1) dengan tiga akses. Pastikan batas r benar dan buat larik yang cukup besar. 🏆
Pertanyaan yang Sering Diajukan
Apakah pelajaran “nCr dengan Faktorial yang Telah Dihitung” gratis?
Ya — teks lengkap “nCr dengan Faktorial yang Telah Dihitung” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “nCr dengan Faktorial yang Telah Dihitung”?
Menghitung kombinasi modulo bilangan prima Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “nCr dengan Faktorial yang Telah Dihitung” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Bekerja Modulo Bilangan Prima
- Eksponensiasi Modular Cepat
- Invers Modular melalui Fermat
- nCr dengan Faktorial yang Telah Dihitung