CSES - Coin Combinations I | Kết hợp đồng xu I
Xem PDF
Điểm:
1200 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Hãy xem xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tính số lượng các cách khác nhau mà bạn có thể tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn.
Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(8\) cách:
- \(2+2+5\)
- \(2+5+2\)
- \(5+2+2\)
- \(3+3+3\)
- \(2+2+2+3\)
- \(2+2+3+2\)
- \(2+3+2+2\)
- \(3+2+2+2\)
Input
- Dòng đầu vào đầu tiên có 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 có \(n\) số nguyên phân biệt biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.
Output
- In một số nguyên: 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
8
Bình luận
anh tăng thêm tí thời gian cho python đi ạ chứ test lớn quá chỉ C++ mới k bị TLE ạ
Python3 và Pypy3 đã được tăng giới hạn thời gian lên 2.0s