【NOIP】1997真题解析 luogu-P2241 统计方形（数据加强版） | GESP三、四级以上可练习

NOIP 1997 普及组第一题（洛谷 P2241 数据加强版），主要考察组合计数原理、循环枚举与数学规律推导。本题既可以通过双重循环枚举矩形的长宽直观求解，也可以通过组合数学与求和公式实现 $\mathcal{O}(\min(n, m))$ 乃至 $\mathcal{O}(1)$ 的高效求解。同时本题也是经典的“防溢出（long long）”教学题。GESP 三、四级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P2241 统计方形（数据加强版）

题目要求

题目背景

1997 年普及组第一题

题目描述

有一个 $n \times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 $n,m$（$n \leq 5000,m \leq 5000$）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

输入输出样例 #1

输入 #1

2 3

输出 #1

8 10

题目分析

这道题目是一道经典的平面几何计数问题。我们需要在 $n \times m$ 个小方格组成的网格中分别统计出：

1. 正方形 的总个数；
2. 长方形（不包含正方形） 的总个数。

1. 核心关系与转化

在几何学中，正方形是特殊的长方形（矩形）。因此： $\text{所有矩形总数（包含正方形）} = \text{正方形个数} + \text{纯长方形个数}$

由此可得： $\text{纯长方形个数} = \text{所有矩形总数} - \text{正方形个数}$

只要我们分别求出 正方形个数 与 矩形总数，即可直接相减得出答案。

2. 矩形总数的计算（组合计数原理）

一个 $n \times m$ 的方格网格由 $(n+1)$ 条横向网格线和 $(m+1)$ 条纵向网格线构成：

• 任意选择 2 条不同的横线（从 $n+1$ 条中选取），即可确定矩形的上下边界，选法共有： $\binom{n+1}{2} = \frac{n(n+1)}{2}$
• 任意选择 2 条不同的竖线（从 $m+1$ 条中选取），即可确定矩形的左右边界，选法共有： $\binom{m+1}{2} = \frac{m(m+1)}{2}$

根据乘法原理，网格中包含的所有矩形总数为： $\text{Total} = \binom{n+1}{2} \times \binom{m+1}{2} = \frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$

3. 正方形个数的计算

正方形要求长和宽相等。设正方形的边长为 $k$，显然 $k$ 的取值范围为 $1 \le k \le \min(n, m)$。

• 对于边长为 $k$ 的正方形：
  • 在水平方向（高为 $n$）上有 $(n - k + 1)$ 种不同的放置位置；
  • 在垂直方向（宽为 $m$）上有 $(m - k + 1)$ 种不同的放置位置；
• 因此，边长为 $k$ 的正方形总共有 $(n - k + 1) \times (m - k + 1)$ 个。
• 累加所有可能的边长 $k$，得到正方形的总数为： $S = \sum_{k=1}^{\min(n, m)} (n - k + 1)(m - k + 1)$

4. 算法实现的三种层次

层次一：$\mathcal{O}(n \times m)$ 双重循环枚举（适合初学者）

• 双重循环分别枚举矩形的长 $i \in [1, n]$ 和宽 $j \in [1, m]$；
• 尺寸为 $i \times j$ 的矩形数量为 $(n - i + 1) \times (m - j + 1)$；
• 若 $i == j$，累加到正方形计数中；若 $i \ne j$，累加到长方形计数中；
• 运算次数约为 $5000 \times 5000 = 2.5 \times 10^7$，在 C++ 1 秒时限内完全可以通过（耗时约 30ms）。

层次二：$\mathcal{O}(\min(n, m))$ 单层循环枚举（推荐做法）

• 利用公式 $\text{Total} = \frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ 在 $\mathcal{O}(1)$ 时间内求出矩形总数；
• 单层循环枚举边长 $k \in [1, \min(n, m)]$，累加求出正方形数量 $S$；
• 纯长方形数量即为 $\text{Total} - S$；
• 循环次数最多仅 $5000$ 次，运行时间在 1ms 以内，代码极其简洁。

层次三：$\mathcal{O}(1)$ 纯数学公式法（极限优化）

将正方形计数式展开： $S = \sum_{k=1}^K (n - k + 1)(m - k + 1) \quad (\text{其中 } K = \min(n, m))$ 设 $A = n + 1, B = m + 1$，则： $(A - k)(B - k) = AB - (A + B)k + k^2$ 代入数列求和公式 $\sum_{k=1}^K k = \frac{K(K+1)}{2}$ 与平方和公式 $\sum_{k=1}^K k^2 = \frac{K(K+1)(2K+1)}{6}$，即可直接在 $\mathcal{O}(1)$ 复杂度内求出 $S$！

⚠️ 核心易错点分析

1. 变量范围与整型溢出（必须使用 long long）

• 题目中 $n, m \le 5000$。
• 极端情况下（$n = 5000, m = 5000$），矩形总数约为： $\text{Total} \approx \frac{5000 \times 5001}{2} \times \frac{5000 \times 5001}{2} \approx 1.25 \times 10^7 \times 1.25 \times 10^7 \approx 1.56 \times 10^{14}$
• 32 位有符号整型 int 的最大值约为 $2.14 \times 10^9$。
• $1.56 \times 10^{14}$ 远超 int 范围，若使用 int 存储或计算，会发生整型溢出导致结果为负数或错误答案。
• 所有涉及结果累加与乘法的变量必须使用 long long 类型！

2. “不包含正方形”的审题陷阱

• 题目第二问明确要求输出“长方形（不包含正方形）”。
• 切勿直接输出所有矩形总数，必须减去正方形的个数。

示例代码

方法一：单层循环 $\mathcal{O}(\min(n, m))$（推荐）

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    // 提高输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    if (!(cin >> n >> m)) {
        return 0;
    }

    // 1. 利用组合公式计算所有矩形（包含正方形）的总数
    long long total_rectangles = (n * (n + 1) / 2) * (m * (m + 1) / 2);

    // 2. 单层循环枚举正方形的边长 k
    long long squares = 0;
    long long limit = min(n, m);
    for (long long k = 1; k <= limit; ++k) {
        squares += (n - k + 1) * (m - k + 1);
    }

    // 3. 纯长方形数量 = 总矩形数 - 正方形数
    long long pure_rectangles = total_rectangles - squares;

    cout << squares << " " << pure_rectangles << "\n";

    return 0;
}

方法二：双重循环 $\mathcal{O}(n \times m)$（直观枚举）

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    cin >> n >> m;

    long long squares = 0;         // 正方形数量
    long long pure_rectangles = 0; // 不含正方形的长方形数量

    // 枚举矩形的长 i 和宽 j
    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; j <= m; ++j) {
            long long count = (n - i + 1) * (m - j + 1);
            if (i == j) {
                squares += count;
            } else {
                pure_rectangles += count;
            }
        }
    }

    cout << squares << " " << pure_rectangles << "\n";

    return 0;
}

方法三：纯数学公式 $\mathcal{O}(1)$（极致常数）

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    cin >> n >> m;

    // 总矩形数
    long long total_rectangles = (n * (n + 1) / 2) * (m * (m + 1) / 2);

    // 正方形总数公式展开计算
    long long K = min(n, m);
    long long A = n + 1;
    long long B = m + 1;

    // sum_1 = sum(k, 1..K) = K*(K+1)/2
    // sum_2 = sum(k^2, 1..K) = K*(K+1)*(2*K+1)/6
    long long sum_1 = K * (K + 1) / 2;
    long long sum_2 = K * (K + 1) * (2 * K + 1) / 6;

    long long squares = K * A * B - (A + B) * sum_1 + sum_2;
    long long pure_rectangles = total_rectangles - squares;

    cout << squares << " " << pure_rectangles << "\n";

    return 0;
}

复杂度对比与总结

知识点拓展总结：

1. 网格计数问题化简法：将二维网格矩形选取转化为一维线段选取的组合问题（乘法原理）；
2. 正反面转化思想：当直接统计某种形状较为复杂时，可用“总方案数 $-$ 反面/特殊方案数”；
3. 数据规模敏感度：时刻关注 $n, m$ 计算产生的结果范围，在竞赛与等级考试中养成对平方、乘积级别结果使用 long long 的良好习惯。