Gửi bài giải
Điểm:
0,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
CONNECT.inp
Output:
CONNECT.out
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Trên một con đường có hai hàng cột đèn chiếu sáng. Hàng bên trái gồm ~n~ cột đèn, hàng bên phải gồm ~m~ cột đèn. Các cột đèn ở bên trái được đặt thẳng hàng với nhau, các cột đèn ở bên phải được đặt thẳng hàng với nhau. Tất cả các cột đèn đều có cùng chiều cao. Một hôm, Huy đi qua con đường này và chợt nghĩ ra một bài toán rất thú vị: Có bao nhiêu cách nối các đường dây điện cho các cột đèn này, sao cho:
- Sử dụng chính xác ~n+m-1~ đường dây điện.
- Mỗi đường dây điện nối chính xác 2 cột đèn.
- Với mọi cặp cột đèn bất kỳ, luôn tồn tại một đường đi giữa hai cột đèn này (trực tiếp qua một đường dây điện hoặc gián tiếp thông qua các dây điện và cột đèn trung gian).
- Khi tất cả các dây điện đều được căng ra, hai dây điện bất kỳ không được có điểm chung nào trừ cột đèn là đầu mút chung của chúng (nếu có).
Huy suy nghĩ rất lâu vẫn chưa thể tìm ra cách giải bài toán. Bạn hãy thử giải bài toán này cùng Huy nhé.
Dữ liệu - Nhập từ tệp văn bản CONNECT.inp
:
- Một dòng duy nhất gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 5000)~.
Kết quả - Ghi ra tệp văn bản CONNECT.out
:
- Một dòng duy nhất gồm phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.
Chấm điểm
Điểm | Ràng buộc bổ sung |
---|---|
~11~ | ~n, m \le 6~ |
~14~ | ~n = 1~ |
~12~ | ~n, m \le 10~ |
~10~ | ~n, m \le 20~ |
~15~ | ~n, m \le 100~ |
~17~ | ~n, m \le 300~ |
~21~ | Không có ràng buộc gì thêm |
Ví dụ
Dữ liệu (CONNECT.inp
)
2 2
Kết quả (CONNECT.out
)
12
Giải thích
Có tổng cộng 12 cách nối dây như liệt kê ở hình trên.
Bình luận