Đếm Cách Đổi Tiền

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved