Hai hình chữ nhật rời nhau
View as PDF
Submit solution
Points:
1.00 (partial)
Time limit:
2.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
C++, Java, Python
Cho một lưới gồm ~n~ hàng và ~m~ cột ô vuông đơn vị. Một hình chữ nhật là một khối ô liên tiếp theo hàng và cột, chứa ít nhất một ô.
Hãy đếm số cách chọn hai hình chữ nhật không có ô chung. Hai hình được phép chạm nhau ở biên, miễn là không dùng chung ô. Cặp hình chữ nhật (~A~, ~B~) và (~B~, ~A~) được tính là cùng một cách.
Cấu hình Input
- Một dòng chứa hai số nguyên ~n~ và ~m~ — lần lượt là số hàng và số cột của lưới.
Cấu hình Output
- In ra số cách chọn modulo ~10⁹ + 7~.
Giới hạn
- ~1 ≤ n, m ≤ 10⁷~.
Ví dụ
Input
1 3
Output
5
Giải thích: Trên lưới một hàng và ba cột, có 5 cặp hình chữ nhật rời nhau: ba cặp gồm hai ô đơn, ô thứ nhất cùng đoạn từ cột 2 đến 3, và đoạn từ cột 1 đến 2 cùng ô thứ ba.
Subtasks
| Subtask | Ràng buộc | Điểm |
|---|---|---|
| 1 | ~1 ≤ n, m ≤ 3~ | 10 điểm |
| 2 | ~1 ≤ n, m ≤ 10³~ | 20 điểm |
| 3 | ~1 ≤ n, m ≤ 2 × 10⁵~ | 30 điểm |
| 4 | ~1 ≤ n, m ≤ 10⁷~ | 40 điểm |
Các test được chấm độc lập; không áp dụng chấm theo batch.
Loading...