💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Đổi Tiền Không Xét Thứ Tự
COINWAYS
## Đề bài Có `n` loại đồng xu, loại thứ `i` có mệnh giá `ci`. Mỗi loại đồng xu có thể sử dụng không giới hạn số lần. Hãy đếm số cách tạo ra tổng tiền đúng bằng `S`. Hai cách chỉ khác nhau về thứ tự được xem là một cách. Ví dụ `1 + 2 + 2` và `2 + 1 + 2` được xem là giống nhau. Vì kết quả có thể rất lớn, hãy in kết quả theo modulo `1 000 000 007`. ## Dữ liệu vào Dòng 1 chứa hai số nguyên `n, S`. Dòng 2 chứa `n` số nguyên dương `c1, c2, ..., cn`. ## Dữ liệu ra In ra số cách tạo tổng `S` theo modulo `1 000 000 007`. ## Giới hạn - `1 ≤ n ≤ 100` - `1 ≤ S ≤ 200000` - `1 ≤ ci ≤ S` - Các mệnh giá có thể không được sắp xếp. ## Phân loại subtask | Subtask | Ràng buộc | Điểm | | --- | --- | --- | | 1 | `n ≤ 5`, `S ≤ 200` | 30% | | 2 | `n ≤ 30`, `S ≤ 20000` | 30% | | 3 | Không có ràng buộc bổ sung | 40% | ## Ví dụ ### Input ```text 3 5 1 2 5 ``` ### Output ```text 4 ``` ### Giải thích Bốn cách là: `1+1+1+1+1`, `1+1+1+2`, `1+2+2`, `5`.
✅ Đã AC: 3 / 6 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng