Đếm Cách Đổi Tiền
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ loại tiền xu với các mệnh giá phân biệt $c_1, c_2, \dots, c_N$ (số lượng mỗi loại vô hạn) và số tiền $S$. Hãy đếm số cách chọn các đồng xu sao cho tổng giá trị bằng $S$ (hai cách chọn chỉ khác nhau về thứ tự các đồng xu được coi là giống nhau). Kết quả lấy modulo $10^9 + 7$.
Cấu trúc con tối ưu: duyệt từng mệnh giá xu $c_i$ ở vòng ngoài, cập nhật $dp[x] = (dp[x] + dp[x - c_i]) \bmod (10^9 + 7)$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $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, \dots, c_N$ ($1 \le c_i \le 10^4$).
Dữ liệu ra
- In ra số cách đổi tiền modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 5\n1 2 5 | 4 |
| 1 3\n2 | 0 |
Giới hạn
- $1 \le N \le 100$
- $0 \le S \le 10^4$
Community Discussion