Deskripsi Untuk Soal Nomor 13 dan 16
Deskripsi Cerita
Pak Dengklek memiliki sebuah kalkulator pengubah basis. Untuk menggunakan kalkulator ini, Pak Dengklek pada awalnya menuliskan sebuah bilangan bulat non-negatif X dalam basis 10. Pak Dengklek kemudian memerintahkan kalkulator tersebut untuk mengubah nilai X ke dalam basis B. Secara cepat, kalkulator tersebut akan menampilkan sebuah string Y tanpa leading zeroes* yang seharusnya merupakan nilai X dalam basis B.
Namun, sangat disayangkan bahwa kalkulator tersebut tidak dapat menampilkan digit selain '0' hingga '9'. Untuk digit di atas '9', kalkulator tersebut akan menuliskan nilai digit tersebut dalam basis 10 tanpa leading zeroes. Misalnya, digit 'A' akan dituliskan sebagai "10", digit 'B' akan dituliskan sebagai "11", dan seterusnya.
Sebagai contoh, Pak Dengklek pada awalnya menuliskan X = 123 456. Pak Dengklek kemudian memerintahkan kalkulator tersebut untuk mengubahnya ke dalam basis B = 16. Bilangan 123 456 dalam basis 16 seharusnya adalah "1E240", namun kalkulator tersebut malah akan menampilkan Y = "114240".
Pak Dengklek kemudian secara cermat mengamati bahwa bisa jadi akan ada banyak bilangan berbeda, yang jika diubah ke dalam suatu basis yang sama, akan menampilkan hasil yang sama pula. Misalnya, 737 856 dalam basis 16 juga akan ditampilkan sebagai "114240". Pun demikian 1 131 072 dalam basis 16 juga akan ditampilkan sebagai "114240".
Diberikan nilai B dan Y, tugas Anda adalah menghitung banyaknya X berbeda, sehingga apabila X diubah ke dalam basis B, maka kalkulator akan menampilkan hasil berupa string Y. Karena jawabannya bisa sangat besar, keluarkan jawabannya modulo 1 000 000 007.
*) Sebagai catatan, sebuah string tidak memiliki leading zeroes apabila digit pertama bukan '0' kecuali jika bilangan tersebut memang 0. Sebagai contoh, "42", "0", dan "1000" merupakan bilangan-bilangan tanpa leading zeroes.
Apabila Pak Dengklek memerintahkan kalkulatornya untuk mengubah nilai 15 015 ke dalam basis 13, maka string apa yang akan ditampilkan oleh kalkulator?
Tuliskan jawaban dalam bentuk STRING tanpa tanda petik.
Asumsikan Pak Dengklek mengubah suatu bilangan ke dalam basis 14 dan kalkulator menampilkan hasil berupa string "123010". Dari 5 skenario berikut, manakah yang tidak mungkin?
Berapa banyak bilangan berbeda yang jika diubah ke dalam basis 16 maka kalkulator akan menampilkan hasil berupa string "71112016"?
Tuliskan jawaban dalam bentuk ANGKA.
Tulislah sebuah program dengan bahasa C/C++ sesuai deskripsi cerita dengan format dan batasan sebagai berikut. Perhatikan bahwa untuk setiap kasus uji berlaku time limit selama 2 detik dan memory limit sebanyak 256 MB.
Format Masukan:
B
YFormat Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya X berbeda, sehingga apabila X diubah ke dalam basis B, maka kalkulator akan menampilkan hasil berupa string Y, modulo 1 000 000 007.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
16 114240 | 3 |
4 114240 | 0 |
10 0 | 1 |
10 1001 | 1 |
1000000 12345678912345678912345678912345678 | 649774399 |
Penjelasan Contoh:
Pada contoh pertama, terdapat 3 kemungkinan X berbeda, yakni 123 456, 737 856, dan 1 131 072; seperti yang telah dijelaskan pada deskripsi cerita.
Pada contoh kedua, tidak ada nilai X yang mungkin karena setiap bilangan yang diubah ke basis 4 pasti hanya memiliki digit 0, 1, 2, atau 3.
Pada contoh ketiga, hanya ada 1 kemungkinan X, yakni 0.
Pada contoh keempat, hanya ada 1 kemungkinan X, yakni 1001.
Pada contoh kelima, sebenarnya terdapat 26 649 774 581 kemungkinan X berbeda, namun perhatikan bahwa jawaban harus dalam modulo 1 000 000 007.
Batasan:
Untuk seluruh kasus uji berlaku:
Batasan Tambahan untuk Subsoal 1 (Mudah)
Pada subsoal ini, untuk seluruh kasus uji berlaku:
Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.
Masuk untuk menulis jawaban