[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, 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×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 (1N,M109;1K20)
  • Trong K dòng sau, dòng thứ i gồm 2 số nguyên dương Xi,Yi (1XiN;1YiM) 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 109+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

Copy
2 3 1
1 1

SAMPLE OUTPUT

Copy
6

Giải thích: Có 6 hình chữ nhật con chứa ô vuông (1,1).


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -3
    tungtungsahur  đã bình luận 3:41:05 ch, 06/05/2025

    tung tung tung sahur