Bedao OI Contest 1 - Bất phương trình tuyến tính
View as PDF
Bất phương trình tuyến tính là bất phương trình có dạng như sau: $$a_1 \times x_1 + a_2 \times x_2 + \ldots + a_n \times x_n \leq m$$ Trong đó ~a_1~, ~a_2~, ~\ldots~, ~a_n~ lần lượt được gọi là hệ số của ~x_1~, ~x_2~, ~\ldots~, ~x_n~; còn ~m~ được gọi là hệ số tự do.
Một nghiệm của bất phương trình là một bộ giá trị (~x_1~, ~x_2~, ~\ldots~, ~x_n~) = (~b_1~, ~b_2~, ~\ldots~, ~b_n~) mà khi thay vào thỏa mãn bất phương trình trên.
Yêu cầu: Cho ~n~ và các hệ số ~a_1~, ~a_2~, ~\ldots~, ~a_n~, ~m~; hãy đếm số nghiệm nguyên dương của bất phương trình ấy.
Input
Dữ liệu vào từ file văn bản nequation.inp
Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~ (~n \leq 10~, ~m \leq 10^9~).
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, ~\ldots~, ~a_n~ (~a_i \leq 10~).
Output
Kết quả in ra file văn bản nequation.out
- In ra một số nguyên duy nhất là số nghiệm nguyên dương của phương trình, vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10\%~ | ~n = 1~ |
| 2 | ~30\%~ | ~n = 2~ |
| 3 | ~30\%~ | ~m \leq 10^6~ |
| 4 | ~30\%~ | Không có điều kiện gì thêm. |
Sample Input 1
5 15
1 2 3 4 5
Sample Output 1
1
Sample Input 2
5 45
1 2 3 2 1
Sample Output 2
79660
Comments