[KHTN - PreTS10 - 2025] Bài 3: REC3
Xem dạng PDF
Gửi bài giải
Điểm:
15,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch, TEXT
Cho một bảng hình chữ nhật gồm ~N~ hàng và ~M~ cột được tạo bởi ~N \times M~ ô vuông đơn vị. Có ~K~ ô trong bảng đã được đánh dấu. Một hình chữ nhật con là một tập hợp các ô vuông đơn vị tạo thành hình chữ nhật nằm hoàn toàn bên trong bảng. Hãy đếm số hình chữ nhật con chứa ít nhất một ô bị đánh dấu.
INPUT
- Dòng đầu tiên ghi 3 số nguyên dương ~N, M, K~ (~1 \le N, M \le 10^9; 1 \le K \le 20~)
- Trong ~K~ dòng sau, dòng thứ ~i~ gồm 2 số nguyên dương ~X_i, Y_i~ (~1 \le X_i \le N; 1 \le Y_i \le M~) là tọa độ của ô vuông thứ ~i~ bị đánh dấu.
OUTPUT
Một số nguyên duy nhất là kết quả của bài toán. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo ~10^9+7~
SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~25~ | ~K = 1~ |
| ~2~ | ~25~ | ~K = 2~ |
| ~3~ | ~50~ | Không có ràng buộc gì thêm. |
SAMPLE INPUT
2 3 1
1 1
SAMPLE OUTPUT
6
Giải thích: Có 6 hình chữ nhật con chứa ô vuông (~1, 1~).
Bình luận
tung tung tung sahur