Masala #HX66JHJYYS
Tangalar yordamida Maqsadli Yig‘indini Toping!
Tasavvur qiling: siz sehrli xazina qutisiga duch keldingiz. Qutini ochish uchun sizda n ta turli qiymatdagi tangalar bor, va har biriga cheksiz marotaba ega bo‘lishingiz mumkin! Qutini ochish siri — tangalarni tartibda joylashtirib, aniq x summani hosil qiladigan tartiblangan va takrorlanmaydigan usullar sonini aniqlash. Qani, eng ko‘p kombinatsiyani kim topadi?
Kiruvchi ma'lumotlar:
- Birinchi qatorda ikki butun son: \(n\) (tangalar soni) va \(x\) (hosil qilinishi kerak bo‘lgan aniq summa).
- Ikkinchi qatorda \(n\) ta butun son: \(c_1, c_2, \ldots, c_n\) – tangalarning qiymatlari (ularning har biri bir-biridan farq qiladi).
- \(1 \le n \le 100\)
- \(1 \le x \le 10^5\)
- \(1 \le c_i \le 10^5\)
Chiquvchi ma'lumotlar:
Faqat bitta son: hamma tartiblangan va takrorlanmaydigan usullar soni, natijani \(10^9+7\) ga bo‘lgandagi qoldiqni chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 9 2 3 5 |
3 |
Izoh:
Misol: agar maqsadli yig‘indi \(9\) bo‘lsa, uni hosil qilish uchun \(3\) ta usul bor:
- \(2 + 2 + 5\)
- \(3 + 3 + 3\)
- \(2 + 2 + 2 + 3\)
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling