Bedao OI Contest 1 - Bất phương trình tuyến tính

View as PDF

Submit solution


Points: 0.80 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: nequation.inp
Output: nequation.out

Author:
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.



  • 8
    llcd2709  commented on Oct. 2, 2023, 11:12 a.m. edited

    Thay gì đếm ~x[1], x[2],...~ sao cho $$a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n] <= m$$ thì có thể chuyển thành đếm ~x[0], x[1],...~ $$x[0] + a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n] = m$$ sau đó có thể dùng automata rồi nhân ma trận để giải

    code: enter link description here