#1478. 「THUPC 2021 初赛」方格游戏

「THUPC 2021 初赛」方格游戏

题目描述

小 F 和小 H 在玩游戏。今天,他们在一个 N×MN\times M 的棋盘上玩游戏。小 H 想考考小 F 的数学能力,但小 F 天生数学就不好,所以想请你帮忙。为了加大难度,小 HH 会在棋盘里面加入 PP 个矩形障碍物。每个矩形障碍物用 UUDDLLRR 来表示,即在第 UU 行到第 DD 行以及在第 LL 列到第 RR 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交,并且所有非障碍物格子之间都能够直接或者间接互达,若两个非障碍物格子有公共边,那么它们直接互达并且它们的距离为 11

现在每一局游戏中,小 F 在棋盘中挑选一个非障碍物格子 XX,小 H 也挑另外一个非障碍物格子 YY,这一局游戏 (X,Y)(X,Y) 的得分就是 XXYY 的最短路径。小 F 需要计算出所有可能的游戏中的得分和,答案模 1,000,000,0071,000,000,007。注意两局游戏中只要挑选的两个格子相同则视为同一局游戏,即 (X,Y)(X, Y) 等同于 (Y,X)(Y,X)

输入格式

第一行三个整数 NN1N1,000,000,0001 \le N \le 1,000,000,000),MM1M1,000,000,0001 \le M \le 1,000,000,000),PP0P100,0000 \le P \le 100,000)。
接下来有 PP 行,每行四个正整数,Ui,DiU_i, D_i1<UiDi<N1 < U_i \le D_i < N),Li,RiL_i, R_i1<LiRi<M1 < L_i \le R_i < M),表示第 ii 个矩形障碍物。对于任意两个不同的矩形障碍物 iijj,都满足 Di+1<UjD_i + 1 < U_j 或者 Dj+1<UiD_j + 1 < U_i,以及 Ri+1<LjR_i + 1 < L_j 或者 Rj+1<LiR_j + 1 < L_i

输出格式

只有一行一个正整数,即所有游戏的得分和模 1,000,000,0071,000,000,007

样例

3 3 1
2 2 2 2

64

距离为 11 的有 88 种。
距离为 22 的有 88 种。
距离为 33 的有 88 种。
距离为 44 的有 44 种。
总共得分为 6464

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。