Mini-proyek Bagian 5: Penghitung Susunan

Proyek penutup. Satu program menjawab empat jenis pertanyaan kombinatorika, semuanya modulo 1.000.000.007 — menggabungkan aturan hitung (Bab 16), permutasi dan kombinasi (Bab 17), serta pangkat dan invers modulo (Bab 14).

Soalnya

Panitia OSN. Panitia ingin satu program penghitung susunan. Ada q pertanyaan, masing-masing diawali angka jenis:

Jenis Masukan tambahan Yang dihitung
1 n r P(n, r) — memilih r dari n dengan urutan
2 n r C(n, r) — memilih r dari n tanpa urutan
3 s banyaknya susunan huruf berbeda dari kata s
4 b k banyaknya jalur pada papan b × k (kanan/bawah)

Semua jawaban dicetak modulo 1.000.000.007.

Batasan. q ≤ 100.000. Untuk jenis 1, 2, dan 4: nilainya sampai 1.000.000. Untuk jenis 3: s hanya berisi huruf besar A–Z, panjang total seluruh kata pada satu berkas masukan tidak lebih dari 1.000.000. Kalau r > n, jawabannya 0.

Contoh masukan:

5
1 10 3
2 10 3
3 OSNOSN
4 3 4
2 1000000 500000

Contoh keluaran:

720
120
90
10
996692777

Yang harus dibuat

  1. Siapkan tabel faktorial sampai 1.000.000 satu kali di awal.
  2. Tulis pangkat_mod dan invers (Bab 14).
  3. Tulis permutasi(n, r) = n! × ((n−r)!)⁻¹.
  4. Tulis kombinasi(n, r) = n! × (r!)⁻¹ × ((n−r)!)⁻¹.
  5. Untuk jenis 3: cacah kemunculan tiap huruf, lalu hitung panjang! × (cacah₁!)⁻¹ × (cacah₂!)⁻¹ × …
  6. Untuk jenis 4: C((b−1) + (k−1), b−1).

Lalu tambahkan penguji: untuk n ≤ 8 dan kata sepanjang ≤ 7, bandingkan jawaban rumus dengan pencacahan langsung (next_permutation untuk jenis 3, mask untuk jenis 2). Penguji ini tidak dicetak ke cout — pakai cerr supaya tidak mengganggu penilaian.

Perhitungan waktu

Bagian Biaya
menyiapkan faktorial 10⁶ langkah, sekali
satu pertanyaan jenis 1, 2, 4 O(log p) ≈ 30 langkah
satu pertanyaan jenis 3 O(panjang kata + 26 log p)

Untuk q = 100.000, totalnya beberapa juta langkah — jauh di dalam batas waktu.

Satu pemanggilan invers berbiaya 30 langkah, dan jenis 2 memerlukan dua. Kalau soalnya lebih ketat, tabel invers faktorial bisa disiapkan sekaligus di awal sehingga setiap pertanyaan menjadi O(1). Coba kalau sudah selesai.

Petunjuk

  • Semua perkalian memakai long long dan % MOD setiap langkah.
  • 'A' sampai 'Z' dicacah dengan array berukuran 26: indeksnya s[i] - 'A'.
  • Faktorial dari 0 adalah 1 — jangan sampai tabelnya dimulai dari 1.
  • Untuk jenis 1 dan 2, periksa r > n lebih dulu dan cetak 0.

File

Compile dan jalankan:

g++ -std=c++17 -O2 -o susunan projects/05-penghitung-susunan/starter.cpp
./susunan < projects/05-penghitung-susunan/contoh-masukan.txt

Sudah selesai?

Kalau keempat jenis benar, penguji tidak menemukan perbedaan, dan kamu bisa menjelaskan kenapa pembagian pada rumus kombinasi harus diganti perkalian invers — proyek ini selesai, dan begitu pula bukunya.

Langkah berikutnya bukan bab baru, melainkan latihan: buka arsip soal OSN di penilai daring yang kamu daftarkan di Bab 01, mulai dari soal tingkat kabupaten, dan kerjakan dengan urutan yang sama seperti di buku ini — baca batasan, hitung jumlah langkah, rencanakan di kertas, tulis brute force, uji, baru percepat.