CSES - Coin Combinations II | Kết hợp đồng xu II
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Xét một hệ thống tiền tệ với \(n\) loại đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Hãy tính số cách khác nhau, không kể thứ tự để tạo ra tổng tiền \(x\) từ những đồng này.
Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(3\) cách:
- \(2+2+5\)
- \(3+3+3\)
- \(2+2+2+3\)
Input
Định dạng đầu vào:
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn.
- Dòng thứ hai chứa \(n\) số nguyên riêng biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.
Output
- In một số nguyên duy nhất: số lượng cách, chia lấy dư cho \(10 ^ 9 + 7\).
Constraints
- \(1\leq n \leq 100\)
- \(1\leq x \leq 10^6\)
- \(1\leq c_i \leq 10^6\)
Example
Sample input
3 9
2 3 5
Sample output
3
Bình luận
ad tăng cho python 3 thêm thời gian được không ạ,chứ nó ra kết quả đúng nhưng bị time:((
Cảm ơn bạn superman1236969 đã góp ý bản dịch!