题解：P3271 [JLOI2016] 方
William2022
·
·
题解
入手
对于这种计数题，可以先去尝试枚举所有可行的正方形，但是本题中点的个数极多，不好计数。
考虑正难则反，既然合法正方形计数难，就枚举非法正方形，可这么做又容易重复。
处理重复可以使用容斥原理。
解法
下文讨论的“正方形”的顶点都在格点上。
记 S_t 表示：枚举所有大小为 t 的被删点集合，对每个集合计算四个顶点包含该集合中全部 t 个被删点的正方形个数，再把这些个数加起来。
根据容斥原理，答案即为 $S_0-S_1+S_2-S_3+S_4$（由于正方形只有四个顶点 $S_5,S_6,\ldots$ 均为 $0$，无需考虑）。
在本题中，分别计算 $S_0,S_1,S_2,S_3,S_4$ 即可，建议自己思考这五种情况，但在这边也提供一下大致解法。
::::info[$S_0$]
一个正方形（红色）可以视作嵌在某个大正方形内。
枚举大正方形边长，即可知道大正方形的数量，再乘上一个大正方形内小正方形的数量。
$$S_0=\sum\limits_{d=2}^{\min(n,m)}(n-d+1)(m-d+1)(d-1)$$
::::
::::info[$S_1$]
枚举一个被删点，计数正方形。
假设枚举到这个红点，然后计数右边绿色正方形可能的数量。
绿色正方形可以视作嵌在一个大正方形内，可以计数大正方形的数量。
本题解代码中对四个方向的大正方形分开计数，且绿色正方形和大正方形重合的情况也是分开的。
::::
::::info[$S_2$]
$O(K^2)$ 枚举每对被删点，计算它们连边作为正方形对角线以及边的情况数。
::::
::::info[$S_3$]
$O(K^2)$ 枚举每对被删点，把它们连边作为正方形对角线，此时使用 `set` 等方式判断该正方形另外两个顶点是否有被删点即可。
::::
::::info[$S_4$]
$O(K^2)$ 枚举每对被删点，把它们连边作为正方形对角线，此时使用 `set` 等方式判断该正方形另外两个顶点是否全为被删点即可。
::::
# 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e8 + 7;
const int N = 2009;
int n, m, K;
int x[N], y[N];
ll S0, S1, S2, S3, S4;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> K;
// 转化为格点数，坐标变为 1‑based
n++; m++;
for (int i = 1; i <= K; i++) {
cin >> x[i] >> y[i];
x[i]++; y[i]++;
}
// 用 set 快速判断一个点是否是被删掉的坏点
set<pair<int, int>> bad;
for (int i = 1; i <= K; i++) {
bad.emplace(x[i], y[i]);
}
// ========== S0 : 所有正方形的总数 ==========
for (int d = 2; d <= min(n, m); d++) {
S0 = (S0 + 1LL * (n - d + 1) * (m - d + 1) % MOD * (d - 1)) % MOD;
}
// ========== S1 : 包含某个被删点的正方形个数之和 ==========
// 对于一个点 x，其垂直方向上方还有 a 格空间，垂直下方还有 b 格空间，水平方向上右边还有 c 格空间，在这个 (a+1+b)*(c+1) 的空间内，calc(a,b,c) 表示有多少一条边包含 x 的大正方形（不包括顶点在 x 上的正方形）（“大正方形”可以见题解S1的大致讲解）。
auto calc = [&](ll a, ll b, ll c) -> ll {
if (c <= 1) return 0;
a = min(a, c - 1);
b = min(b, c - 1);
ll ans = a * b;
ll t = max(b - (c - a), 0LL);
ans -= t * (t + 1) / 2;
return ans;
};
for (int i = 1; i <= K; i++) {
ll cnt = 0;
// 斜正方形：大正方形的四个方向
cnt += calc(x[i] - 1, n - x[i], m - y[i]);
cnt += calc(x[i] - 1, n - x[i], y[i] - 1);
cnt += calc(y[i] - 1, m - y[i], n - x[i]);
cnt += calc(y[i] - 1, m - y[i], x[i] - 1);
// 正放正方形：i号点是正方形顶点
cnt += min(x[i] - 1, y[i] - 1);
cnt += min(x[i] - 1, m - y[i]);
cnt += min(n - x[i], y[i] - 1);
cnt += min(n - x[i], m - y[i]);
cnt %= MOD;
S1 = (S1 + cnt) % MOD;
}
// ========== S2, S3, S4 : 枚举坏点对生成正方形 ==========
// 情形 1 : 以 (x[i],y[i]) 和 (x[j],y[j]) 为正方形的一条边
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
if (i == j) continue;
int dx = x[j] - x[i];
int dy = y[j] - y[i];
int px1 = x[i] + dy;
int py1 = y[i] - dx;
int px2 = x[j] + dy;
int py2 = y[j] - dx;
if (px1 < 1 || px1 > n) continue;
if (px2 < 1 || px2 > n) continue;
if (py1 < 1 || py1 > m) continue;
if (py2 < 1 || py2 > m) continue;
S2++;
}
}
// 情形 2 : 以 (x[i],y[i]) 和 (x[j],y[j]) 为对角线
for (int i = 1; i <= K; i++) {
for (int j = i + 1; j <= K; j++) {
int sumx = x[i] + x[j];
int sumy = y[i] + y[j];
int dx = x[i] - x[j];
int dy = y[i] - y[j];
// 另外两个顶点的 2 倍坐标
int px1_2 = sumx - dy;
int py1_2 = sumy + dx;
int px2_2 = sumx + dy;
int py2_2 = sumy - dx;
if (px1_2 & 1 || py1_2 & 1 || px2_2 & 1 || py2_2 & 1) continue;
int px1 = px1_2 / 2, py1 = py1_2 / 2;
int px2 = px2_2 / 2, py2 = py2_2 / 2;
if (px1 < 1 || px1 > n) continue;
if (px2 < 1 || px2 > n) continue;
if (py1 < 1 || py1 > m) continue;
if (py2 < 1 || py2 > m) continue;
S2++;
bool A = bad.count({px1, py1});
bool B = bad.count({px2, py2});
S3 += A + B;
S4 += (A && B);
}
}
S4 /= 2; // 每个四坏点正方形被两条对角线重复计算了一次
// ========== 容斥原理 ==========
S0 %= MOD; S1 %= MOD; S2 %= MOD; S3 %= MOD; S4 %= MOD;
ll ans = (S0 - S1 + S2 - S3 + S4) % MOD;
ans = (ans + MOD) % MOD;
cout << ans << "\n";
return 0;
}
```
::::info[AI 使用声明]
代码由 Deepseek 优化过码风，部分注释也由其生成。
::::