自动搬运

查看原文

来自洛谷，原作者为

	wrpwrp Cai

搬运于2025-08-24 22:26:58，当前版本为作者最后更新于2021-12-21 22:01:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

小 F 和小 H 在玩游戏。今天，他们在一个 $N \times M$ 的棋盘上玩游戏。小 H 想考考小 F 的数学能力，但小 F 天生数学就不好，所以想请你帮忙。

为了加大难度，小 H 会在棋盘里面加入 $P$ 个矩形障碍物。每个矩形障碍物用 $U$、$D$、$L$、$R$ 来表示，即在第 $U$ 行到第 $D$ 行以及在第 $L$ 列到第 $R$ 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交，并且所有非障碍物格子之间都能够直接或者间接互达，若两个非障碍物格子有公共边，那么它们直接互达并且它们的距离为 1 。

现在每一局游戏中，小 F 在棋盘中挑选一个非障碍物格子 $X$，小 H 也挑另外一个非障碍物格子 $Y$，这一局游戏 $(X,Y)$ 的得分就是 X 到 Y 的最短路径。小 F 需要计算出所有可能的游戏中的得分和，答案模 $1,000,000,007$。

注意两局游戏中只要挑选的两个格子相同则视为同一局游戏，即 $(X, Y)$ 等同于 $(Y, X)$。

第一行三个整数 $N(1 \leq N \leq 1,000,000,000)$，$M(1 \leq M \leq 1,000,000,000)$，$P(0 \leq P \leq 100,000)$。

接下来有 $P$ 行，每行四个正整数，$U_i$，$D_i (1<U_i \leq D_i<N)$，$L_i$，$R_i(1<L_i \leq R_i<M)$，表示第 $i$ 个矩形障碍物。

对于任意两个不同的矩形障碍物 $i$ 和 $j$，都满足 $D_i+1<U_j$ 或者 $D_j+1<U_i$，以及 $R_i+1<L_j$ 或者 $R_j+1<L_i$。

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

距离为 1 的有 8 种。

距离为 2 的有 8 种。

距离为 3 的有 8 种。

距离为 4 的有 4 种。

总共得分为 64 。

题解

分类讨论题。 终于见到阳间的分类讨论题了， md模拟赛里面的我就没对过 。

纪念第一个自己推出来的分类讨论， 虽然好像并没有什么难度

考虑先不考虑障碍物直接求每两两之间不考虑障碍物的最短路， 然后减去障碍物里面到外面的， 然后加上绕路的部分， 一点一点讨论。

不考虑障碍物的两两最短路之和

考虑对于横坐标和纵坐标分别枚举长度计算贡献得到 :

$$\sum_{i = 0}^{n - 1}m^2(n -i)i + \sum_{i = 0}^{m - 1}n^2(m - i)i = \frac{m^2(n^3 - n) + n^2(m^3 - m)}{6} $$

计算障碍物内外的最短路之和

只考虑当前一个障碍物， 当前障碍物为 $(l_x, r_x, l_y, r_y)$ 分别表示横纵坐标。

先考虑横坐标的贡献， 记 $S1(n) = \sum_{i = 1}^ni$, $S2 = \sum_{i = 1}^ni^2$。

$$\sum_{i = l_x} ^{r_x}\sum_{j = 1}^n|j - i|m(r_y - l_y + 1) $$

令 $m(r_y - l_y + 1) = C$ 最后乘上。

$$\sum_{i = l_x} ^{r_x}\sum_{j = 1}^n|j - i|$$ $$= \sum_{i = l_x}^{r_x}\sum_{j = 1}^{i - 1} i - j + \sum_{i = l_x}^{r_x}\sum_{j = i +1}^{n} j - i $$$$= \sum_{i = l_x}^{r_x}i(i - 1) - \sum_{i = l_x} ^ {r_x} \frac{i(i - 1)}{2} - \sum_{i = l_x}^{r_x}(n - i)i + \sum_{i = l_x}^{r_x}\frac{(n - i)(i + 1 + n)}{2} $$$$= \frac{1}{2} \times \sum_{i = l_x}^{r_x} 2i^2 - 2in +n^2 + n - 2i $$

所以 $x$ 轴的贡献是 ：

$$\frac{1}{2} \times C \times [(r_x - l_x + 1) \times (n^2 + n) + 2 (S2(r_x) - S2(l_x - 1)) - (2n + 2)(S1(r_x) - S1(l_x - 1))] $$

同理 $y$ 轴的贡献就是 ：

$$\frac{1}{2} \times C \times [(r_y - l_y + 1) \times (m^2 + m) + 2 (S2(r_y) - S2(l_y - 1)) - (2m + 2)(S1(r_y) - S1(l_y - 1))] $$

计算障碍物到自己里面的最短路之和

就是一开始的计算全局不考虑障碍物的路径长度之和的做法。

计算当前障碍物里面到外面所有障碍物路径之和

有一个经典的操作。

同样把 $x$ 轴和 $y$ 轴分开考虑， 以 $x$ 轴为例。

我们把矩形按照 $x$ 轴排序， 维护之前的点数和 $cnt$ 以及 $x$ 坐标和 $sum_x$，记当前障碍的点数为 $c$， 当前的障碍的 $x$ 坐标和是 $s$ 。

把答案加上 $cnt \times s - sum_x\times c$ 即可。

计算绕远路的部分

同样不妨考虑 $x$ 轴的贡献， 设障碍物的宽为 $l$ ， 左边有 $L$ 个数， 右边有 $R$ 个数， $C = L \times R$ 。可以写出答案 ：

$$\sum_{i = 1}^l\sum_{j = 1}^l2\times \min(i, l - i + 1, j, l - j + 1) $$

不妨设 $l$ 为偶数， $t = \frac{l}{2}$ 。

$$\sum_{i = 1}^l\sum_{j = 1}^l2\times \min(i, l - i + 1, j, l - j + 1) $$$$=4\times \sum_{i = 1}^t\sum_{j = 1}^t2 \min (i, j) $$$$= 4\times ((2t + 1)\frac{t(t+ 1)}{2} - \frac{t(t + 1)(2t + 1)}{6}) $$

考虑 $l$ 是奇数的情况， 只要加一个 $(l +1)^2\times \frac{1}{2}$ 即可， 具体只要观察一下会多出来哪些东西就好了。

code