Số cách đổi tiền không phân biệt thứ tự

Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Có $N$ loại đồng xu với các mệnh giá đôi một khác nhau là $c_1, c_2, \dots, c_N$. Mỗi loại đồng xu có số lượng không giới hạn.

Hãy đếm số cách chọn các đồng xu sao cho tổng giá trị của chúng đúng bằng $S$. Hai cách chọn được coi là giống nhau nếu số lượng mỗi loại đồng xu được chọn là như nhau (không phân biệt thứ tự). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $S$ ($1 \le N \le 100$, $0 \le S \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^5$).
Dữ liệu ra
  • In ra số cách đổi tiền chia lấy dư cho $10^9 + 7$.
Ví dụ
Input Output
3 5
1 2 5
4
Giới hạn
  • $1 \le N \le 100$
  • $0 \le S \le 10^5$
  • $1 \le c_i \le 10^5$
Draft saved