题意简述
\(n\) 行 \(m\) 列构成 \(nm\) 个格点，在其中指定 \(k\) 个障碍点。每行、每列之间的距离为 \(1\)，每次任意选取两个非障碍点，计算这两个点的曼哈顿距离，求所有选法的距离之和。
分析
由容斥原理，答案为「任意两点之间的距离之和」\(-\)「每个障碍点到其他所有点的距离之和」\(+\)「任意两障碍点之间的距离之和」。下面分别考虑这三部分怎么求。
前置知识
\[\sum_{i=1}^n i = \frac{n(n+1)}{2} \\ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \]两式可以由数学归纳法证明。
任意两点之间的距离之和
显然行和列是等价的，下面考虑行之间的距离，即纵坐标对答案的贡献。
\[i \; \overbrace{\circ \circ \cdots \circ \circ}^m \\ \cdots \\ j \circ \circ \cdots \circ \circ \]如图，我们任意选取两行，不妨设为第 \(i\) 行和第 \(j\) 行（\(1 \le i < j \le n\)）。在第 \(i\) 行和第 \(j\) 行各任选 \(1\) 个点，由乘法原理知共有 \(m^2\) 种选法。显然这两点纵坐标的差为 \(j-i\)。所以，第 \(i\) 行和第 \(j\) 行的纵坐标对答案的贡献为 \(m^2 \cdot (j-i)\)。
枚举 \(i, j\)，我们得到纵坐标对答案的贡献为：
\[m^2 \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (j-i) \]考虑化简：
\[\begin{aligned} m^2 \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (j-i) &= m^2 \sum_{i=1}^{n-1} \sum_{i=1}^{n-i} j \\ &= m^2 \begin{pmatrix} \begin{aligned} &1+2+ \cdots +(n-2)+(n-1) \\ +&1+2+ \cdots +(n-2) \\ +& \cdots \\ +&1+2 \\ +&1 \end{aligned} \end{pmatrix}\\ &= m^2 \sum_{i=1}^{n-1} [i \cdot (n-i)] \\ &= m^2 \sum_{i=1}^{n-1} [in-i^2] \\ &= m^2 n \sum_{i=1}^{n-1} i-m^2 \sum_{i=1}^{n-1} i^2 \end{aligned} \]这样化简的好处是可以直接套用两个公式，时间复杂度 \(O(1)\) 。
横坐标同理。综上，「任意两点之间的距离之和」为
\[m^2 n \sum_{i=1}^{n-1} i-m^2 \sum_{i=1}^{n-1} i^2+n^2 m \sum_{i=1}^{m-1} i-n^2 \sum_{i=1}^{m-1} i^2 \]每个障碍点到其他所有点的距离之和
直接枚举每个障碍点，显然 \(\sum_{i=1}^k \sum_{x=1}^n \sum_{y=1}^m (|x_i-x|+|y_i-y|)\) 即为所求。
类似地，考虑化简：
\[\begin{aligned} \sum_{i=1}^k \sum_{x=1}^n \sum_{y=1}^m (|x_i-x|+|y_i-y|) &= \sum_{i=1}^k (\sum_{x=1}^n \sum_{y=1}^m |x_i-x|+\sum_{x=1}^n \sum_{y=1}^m |y_i-y|) \\ &= \sum_{i=1}^k (m \sum_{x=1}^n |x_i-x|+n \sum_{y=1}^m |y_i-y|) \\ &= \sum_{i=1}^k (m \sum_{x=1}^{x_i-1} (x_i-x)+m \sum_{x = x_i+1}^{n} (x-x_i)+n \sum_{y=1}^{y_i-1} (y_i-y)+n \sum_{y = y_i+1}^{m} (y-y_i)) \\ &= \sum_{i=1}^k (m \sum_{x=1}^{x_i-1} x+m \sum_{x=1}^{n-x_i}+n \sum_{y=1}^{y_i-1} y+n \sum_{y=1} ^ {m-y_i}) \end{aligned} \]时间复杂度 \(O(k)\)。
任意两障碍点之间的距离之和
将 \(x\) 从小到大排序。设 \(f_i = \sum_{i=1}^{i-1} (x_i-x_j)\)。特别地，\(f_1 = 0\)。则显然 \(\sum_{i=1}^{k} f_i\) 即为所求。
有递推式 \(f_i = f_{i-1}+(i-1) \cdot (x_i-x_{i-1})\)。
证明：
\[\begin{aligned} f_i &= \sum_{i=1}^{i-1} (x_i-x_j) \\ &= \sum_{i=1}^{i-2} (x_i-x_j)+x_i-x_{i-1} \\ &= \sum_{i=1}^{i-2} [(x_i-x_{i-1})+(x_{i-1}-x_j)]+x_i-x_{i-1} \\ &= \sum_{i=1}^{i-2} (x_i-x_{i-1})+f_{i-1}+x_i-x_{i-1} \\ &= f_{i-1}+(i-1) \cdot (x_i-x_{i-1}) \end{aligned} \]因此递推 \(f\) 的同时累加答案即可，\(y\) 同理。
时间复杂度 \(O(k \log k)\)。
代码
#include <iostream>
#include <algorithm>
const int MOD = 1e9 + 7;
int x[500005], y[500005];
int sum1(int n) // 公式 1
{
return 1ll * n * (n + 1) / 2 % MOD;
}
int sum2(int n) // 公式 2
{
// 注意被 6 整除的问题
// n * (n + 1) 一定被 2 整除, 因此只需讨论 n, (n + 1), (2 * n + 1) 中哪个因式被 3 整除
if (n % 3 == 1) // 此时 (2 * n + 1) 被 3 整除
return 1ll * n * (n + 1) / 2 % MOD * (2 * n + 1) / 3 % MOD;
return 1ll * n * (n + 1) / 6 % MOD * (2 * n + 1) % MOD; // 否则 n 和 (n + 1) 一定有一个被 3 整除
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m, k;
long long f, ans = 0;
std::cin >> n >> m >> k;
for (int i = 1; i <= k; i++)
std::cin >> x[i] >> y[i];
// 任意两点之间的距离之和
ans += 1ll * m * m % MOD * n % MOD * sum1(n - 1) % MOD;
ans -= 1ll * m * m % MOD * sum2(n - 1) % MOD;
ans += 1ll * n * n % MOD * m % MOD * sum1(m - 1) % MOD;
ans -= 1ll * n * n % MOD * sum2(m - 1) % MOD;
ans = (ans % MOD + MOD) % MOD; // 取模时注意负数
// 每个障碍点到其他所有点的距离之和
for (int i = 1; i <= k; i++)
{
ans -= 1ll * m * sum1(x[i] - 1) % MOD;
ans -= 1ll * m * sum1(n - x[i]) % MOD;
ans -= 1ll * n * sum1(y[i] - 1) % MOD;
ans -= 1ll * n * sum1(m - y[i]) % MOD;
ans = (ans % MOD + MOD) % MOD; // 取模时注意负数
}
// 任意两障碍点之间的距离之和
f = 0;
std::sort(x + 1, x + k + 1);
for (int i = 2; i <= k; i++)
{
f += 1ll * (i - 1) * (x[i] - x[i - 1]) % MOD;
f %= MOD;
ans += f;
ans %= MOD;
}
f = 0;
std::sort(y + 1, y + k + 1);
for (int i = 2; i <= k; i++)
{
f += 1ll * (i - 1) * (y[i] - y[i - 1]) % MOD;
f %= MOD;
ans += f;
ans %= MOD;
}
std::cout << ans << "\n";
return 0;
}