16. Aturan penjumlahan dan perkalian — Pembahasan PR

Soal 1 dikerjakan di kertas. Berkas .cpp untuk soal 2 sampai tantangan ada di exercises/16/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Untuk soal kertas, tulis dulu jawabanmu, baru bandingkan — membaca jawaban orang lain terasa jelas padahal belum tentu bisa diulang sendiri. Bagian Uji berisi masukan dan keluaran yang sudah diperiksa untuk soal berkode.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/16/homework/solutions/02-periksa.cpp
./jawab

Soal 1 — Hitung di kertas

a. Bilangan tiga digit yang semua digitnya genap → 100.

Digit ratusan tidak boleh nol, jadi pilihannya {2, 4, 6, 8} — empat cara. Digit puluhan dan satuan boleh nol, jadi {0, 2, 4, 6, 8} — lima cara masing-masing. Aturan perkalian: 4 × 5 × 5 = 100.

b. Bilangan tiga digit dengan minimal satu angka 7 → 252.

Lewat komplemen. Seluruh bilangan tiga digit ada 900. Yang tidak mengandung 7 sama sekali: ratusan punya 8 pilihan (1–9 tanpa 7), puluhan dan satuan masing-masing 9 (0–9 tanpa 7) → 8 × 9 × 9 = 648. Jawabannya 900 − 648 = 252.

c. Dari 1 sampai 1.000, habis dibagi 4 atau 6 → 333.

⌊1000/4⌋ = 250, ⌊1000/6⌋ = 166, dan irisannya adalah kelipatan KPK(4, 6) = 12: ⌊1000/12⌋ = 83. Jadi 250 + 166 − 83 = 333.

Perhatikan irisannya memakai KPK, bukan hasil kali 4 × 6 = 24. Memakai 24 memberi jawaban salah 375.

d. Paket menu → 36.

Satu makanan (4 cara) dan satu minuman (3 cara) wajib. Hidangan penutup punya 3 keadaan: ambil yang pertama, ambil yang kedua, atau tidak ambil. Jadi 4 × 3 × 3 = 36.

Ini gabungan dua aturan: "boleh diambil atau tidak" adalah aturan penjumlahan (2 + 1) yang lalu masuk ke dalam perkalian.

Soal 2 — Periksa dengan program

Cara berpikir. Untuk setiap bagian, tulis perulangan yang benar-benar memeriksa seluruh 900 bilangan (atau seluruh kombinasi menu). Kalau rumus dan cacahan berbeda, rumusnyalah yang hampir selalu salah.

Pembahasan.

int b = 0;
for (int n = 100; n <= 999; n++) {
    int r = n / 100, p = (n / 10) % 10, s = n % 10;
    if (r == 7 || p == 7 || s == 7) b++;
}
cout << b << " " << 900 - 8 * 9 * 9 << "\n";   // 252 252

Uji. Program jawabannya mencetak kedua angka berdampingan:

a: 100 (rumus 4*5*5 = 100)
b: 252 (rumus 900 - 8*9*9 = 252)
c: 333 (rumus 250 + 166 - 83 = 333)
d: 36 (rumus 4*3*3 = 36)

Kalau salah satu baris tidak cocok, yang salah belum tentu rumusnya — pencacahan langsungnya juga bisa salah, misalnya karena rentang perulangannya 100 sampai 1000 dan bukan 100 sampai 999. Kebiasaan yang benar: cari perbedaannya pada kasus terkecil, bukan langsung menyalahkan salah satu pihak.

Kesalahan umum.

• Pada bagian (d), menghitung hidangan penutup sebagai 2 pilihan, sehingga jawabannya 24. Kata "boleh diambil atau tidak" menambah satu keadaan.
• Menulis pencacahan yang memakai rumus yang sama dengan jawaban kertas. Pencacahan harus polos — periksa satu per satu.

Soal 3 — Kata sandi

Soal. Kata sandi sepanjang n dari k huruf, minimal satu huruf a, modulo 10⁹ + 7.

Cara berpikir. Komplemen: seluruh kata sandi kⁿ, yang tanpa huruf a ada (k−1)ⁿ. Jawabannya selisihnya. Karena n sampai 10¹⁸, keduanya dihitung dengan pangkat modulo cepat (Bab 14).

Satu jebakan modulo: hasil pengurangan bisa negatif setelah di-modulo. Rapikan dengan menambah MOD sekali lagi.

Pembahasan.

long long semua = pangkat_mod(k, n, MOD);
long long tanpa_a = pangkat_mod(k - 1, n, MOD);

cout << ((semua - tanpa_a) % MOD + MOD) % MOD << "\n";

Periksa dengan 4 26: hasilnya 66.351, sama dengan pencacahan langsung di contoh bab.

Uji.

Baris pertama layak diuji karena rumus komplemen di sana menghasilkan 1 − 0: kalau hanya ada satu huruf dan huruf itu a, tidak ada kata sandi yang "tanpa a". Baris terakhir menguji pangkat modulo cepat — dengan perulangan biasa, program itu tidak akan pernah selesai.

Kesalahan umum.

• Mencetak semua - tanpa_a tanpa merapikan tanda negatif.
• Menghitung kⁿ dengan perulangan n kali.
• Lupa kasus k = 1: seluruh kata sandi hanya berisi huruf a, dan (k−1)ⁿ = 0 — rumusnya tetap benar.

Soal 4 — Inklusi-eksklusi

Soal. Dari 1 sampai n (≤ 10¹⁸), yang habis dibagi p atau q.

Cara berpikir. Banyaknya kelipatan p sampai n adalah n / p (pembagian bulat). Irisannya adalah kelipatan KPK(p, q).

Jebakan besarnya: KPK dari dua bilangan mendekati 10¹⁸ jauh melebihi batas long long. Padahal kalau KPK-nya saja sudah lebih besar dari n, suku irisannya bernilai nol — nilai tepatnya tidak diperlukan. Jadi periksa dulu apakah perkaliannya akan melewati n:

Pembahasan.

long long calon = p / fpb(p, q);
long long jawab = n / p + n / q;

if (calon <= n / q) {          // calon * q tidak akan melebihi n
    long long k = calon * q;
    jawab -= n / k;
}

cout << jawab << "\n";

Periksa: 100 3 5 memberi 47; 1000 4 6 memberi 333.

Uji.

Baris kedua adalah pemeriksaan silang yang bagus: jawabannya harus sama dengan hitungan tanganmu di soal 1c. Baris ketiga adalah alasan KPK dihitung dengan p / fpb(p, q) * q: dengan p * q lebih dulu, bilangan sebesar itu sudah meluap sebelum sempat dipakai.

Kesalahan umum.

• Memakai p * q sebagai irisan, bukan KPK. Salah kecuali p dan q saling prima.
• Menghitung KPK tanpa penjagaan luapan, lalu mendapat angka negatif yang membuat n / k bernilai aneh.
• Mencacah satu per satu dengan perulangan sampai n. Untuk 10¹⁸, mustahil.

Tantangan — Tiga himpunan

Soal. Habis dibagi minimal satu dari tiga bilangan.

Rumusnya (tujuh suku).

n/p + n/q + n/r
  − n/KPK(p,q) − n/KPK(p,r) − n/KPK(q,r)
  + n/KPK(p,q,r)

Polanya: suku tunggal ditambah, suku pasangan dikurangi, suku bertiga ditambah lagi. Untuk m himpunan ada 2ᵐ − 1 suku, dengan tanda berganti menurut banyaknya himpunan yang terlibat.

Cara berpikir. Setiap KPK dihitung dengan penjagaan yang sama seperti soal 4. KPK bertiga dihitung bertahap: KPK(KPK(p, q), r) — dan kalau KPK pasangannya saja sudah melebihi n, sukunya bisa dilewati.

Pembahasan. Lihat 05-tiga-himpunan.cpp. Bagian pemeriksaannya:

if (n <= 10000) {
    long long cacah = 0;
    for (long long i = 1; i <= n; i++)
        if (i % p == 0 || i % q == 0 || i % r == 0) cacah++;
    cout << "cacah langsung: " << cacah << "\n";
}

Periksa: 100 2 3 5 memberi 74 dari rumus dan 74 dari pencacahan; 10000 4 6 15 memberi 3.666 dari keduanya.

Uji. Program jawabannya mencetak rumus dan pencacahan langsung sekaligus:

Kasus kedua sengaja memakai tiga bilangan yang tidak saling prima: irisan 4 dan 6 adalah kelipatan 12 (bukan 24), irisan 4 dan 10 adalah kelipatan 20 (bukan 40), dan irisan ketiganya kelipatan 60. Rumus yang memakai hasil kali alih-alih KPK akan meleset di sini, sementara pada 100 2 3 5 ia kebetulan benar karena ketiganya saling prima.

Kesalahan umum.

• Menukar tanda pada suku bertiga. Kalau + diganti −, bilangan yang habis dibagi ketiganya menjadi tidak terhitung sama sekali.
• Menghitung KPK bertiga sebagai p * q * r.
• Lupa menguji rumusnya dengan pencacahan langsung. Rumus tujuh suku mudah salah ketik, dan pencacahan n ≤ 10.000 menangkapnya dalam sedetik.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/16/osn/solutions/.

Soal 1 — Bendera Berwarna

Cara berpikir. Warnai dari kiri ke kanan. Jalur pertama tidak punya tetangga kiri, jadi bebas: K pilihan. Setiap jalur berikutnya hanya dilarang satu warna, yaitu warna tetangga kirinya — berapa pun warna itu, larangannya selalu satu, jadi pilihannya selalu K − 1.

Karena setiap keputusan berdiri sendiri setelah keputusan sebelumnya ditetapkan, aturan perkalian berlaku:

K × (K − 1) × (K − 1) × … = K × (K − 1)^(N−1)

Pangkat sebesar 10¹⁸ dihitung dengan pangkat modulo cepat dari Bab 14.

Pembahasan.

long long hasil = k % MOD * pangkat(k - 1, n - 1) % MOD;
cout << hasil << "\n";

Kasus tepi. Rumusnya sudah benar untuk keduanya tanpa cabang tambahan:

• N = 1: pangkatnya menjadi (K − 1)^0 = 1, jadi jawabannya K.
• K = 1 dan N ≥ 2: pangkatnya 0^(N−1) = 0, jadi jawabannya 0 — memang tidak ada bendera sah karena dua jalur bersebelahan pasti sewarna.

Uji.

Untuk 3 3, jawabannya bisa dicacah dengan tangan atau dengan program pencacah — dan memang 12.

Kesalahan umum.

• Menulis K^N, lupa larangan tetangga.
• Menulis K × (K − 1)^N, salah satu pangkat.
• Lupa k % MOD sebelum dikalikan. Untuk K ≤ 10⁹ hasilnya kebetulan masih benar, tetapi kebiasaan menyisakan setiap faktor lebih aman.

Soal 2 — Sandi Dua Huruf Wajib

Cara berpikir. Menghitung langsung "memuat a dan memuat b" sulit. Hitung komplemennya.

Sebut S himpunan semua kata sepanjang N, banyaknya K^N. Sebut A himpunan kata yang tidak memuat a, banyaknya (K − 1)^N karena setiap posisi punya K − 1 pilihan. Sebut B himpunan kata yang tidak memuat b, banyaknya juga (K − 1)^N.

Kata yang tidak sah adalah anggota A atau anggota B. Menurut inklusi-eksklusi:

|A ∪ B| = |A| + |B| − |A ∩ B| = 2(K−1)^N − (K−2)^N

Irisan A ∩ B adalah kata yang tidak memuat a maupun b, banyaknya (K − 2)^N. Jadi jawabannya:

K^N − 2(K−1)^N + (K−2)^N

Pembahasan.

long long semua = pangkat(k, n);
long long tanpaSatu = pangkat(k - 1, n);
long long tanpaKeduanya = pangkat(k - 2, n);

long long hasil = ((semua - 2 * tanpaSatu % MOD) % MOD + tanpaKeduanya) % MOD;
hasil = (hasil % MOD + MOD) % MOD;

Baris terakhir yang membuat hasilnya tidak pernah negatif. Tanpa itu, program bisa mencetak angka negatif untuk masukan yang seluruhnya sah — gejala yang tidak muncul pada contoh soal.

Uji.

Kasus 3 2 layak dicacah dengan tangan: dari delapan kata atas a dan b, yang memuat keduanya adalah semuanya kecuali aaa dan bbb, jadi 6.

Kesalahan umum.

• Memakai rumus K^N − (K−2)^N. Itu jawaban untuk "memuat a atau b", soal yang berbeda.
• Lupa penyesuaian + MOD setelah pengurangan.
• Menghitung 2 * tanpaSatu tanpa % MOD, yang untuk nilai mendekati modulus masih aman di long long tetapi merusak bentuk baku yang seharusnya dibiasakan.

Soal 3 — Pasangan Berjumlah Kelipatan K

Cara berpikir. x + y habis dibagi K hanya ditentukan oleh sisa x dan sisa y, bukan oleh nilainya. Jadi kelompokkan bilangan 1 sampai N menurut sisanya terhadap K, lalu pasangkan kelompoknya.

Kalau x bersisa r, maka y harus bersisa K − r — kecuali untuk r = 0, yang pasangannya juga 0. Bentuk (K − r) % K menangani keduanya sekaligus.

Banyaknya bilangan 1 sampai N yang bersisa r:

• untuk r = 0: ⌊N / K⌋
• untuk r ≥ 1: ⌊(N − r) / K⌋ + 1, dan 0 kalau r > N

Jawabannya adalah jumlah cacah[r] × cacah[(K − r) % K] untuk seluruh r. Karena pasangannya terurut, tidak ada pembagian dua di akhir.

Pembahasan.

vector<long long> cacah(k, 0);
cacah[0] = n / k;
for (long long r = 1; r < k; r++) {
    if (r > n) break;
    cacah[r] = (n - r) / k + 1;
}

long long hasil = 0;
for (long long r = 0; r < k; r++) {
    hasil += cacah[r] * cacah[(k - r) % k];
}

Biayanya sebanding dengan K, bukan N — 10⁶ langkah untuk batasan terbesar.

Besarnya jawaban. Kasus terbesar adalah K = 1, saat semua pasangan memenuhi: N² = 10¹⁸. Muat di long long, dan inilah alasan batasan N pada soal ini lebih kecil daripada dua soal sebelumnya.

Uji.

Kasus 7 10 menguji sisa yang tidak pernah muncul: kelompok r = 8 dan seterusnya kosong, dan perkaliannya harus menghasilkan nol, bukan membaca di luar array.

Kesalahan umum.

• Memakai cacah[k - r] tanpa % k, yang untuk r = 0 membaca cacah[k] — di luar batas.
• Membagi hasil dengan 2. Pasangannya terurut, jadi tidak ada pembagian.
• Memeriksa semua pasangan (x, y) dengan perulangan bersarang.

Kalau masih tersendat

• Bingung menjumlahkan atau mengalikan → Bab 16, tabel "atau/dan" dan gambar pohonnya.
• Ada yang terhitung dua kali → Bab 16, bagian Ketika kelompoknya beririsan.
• Soal "minimal satu" terasa berat → Bab 16, teknik komplemen.

Kebiasaan yang paling berguna dari bab ini: setiap rumus cacahan diperiksa dengan pencacahan langsung pada data kecil sebelum dipakai untuk data besar.