Đếm số cách đổi tiền
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho $N$ mệnh giá tiền phân biệt $C_1, C_2, \dots, C_N$ với số lượng không giới hạn mỗi loại. Hãy đếm số cách khác nhau để tạo thành tổng tiền $S$ (hai cách được coi là giống nhau nếu số lượng tờ tiền mỗi mệnh giá là như nhau, không phân biệt thứ tự).
Kết quả lấy phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, S$ ($1 \le N \le 100$, $0 \le S \le 10^4$).
- Dòng thứ hai chứa $N$ số nguyên dương phân biệt $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^4$).
Dữ liệu ra
Một số nguyên duy nhất là số cách đổi tiền modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
3 5<br>1 2 5 |
4 |
Giới hạn
- $1 \le N \le 100$
- $0 \le S \le 10^4$
Community Discussion