企业官网建设流程全解析

洛谷 P2241 这道题，题号里有三样东西很容易让人轻敌：NOIP 1997、普及组、统计方形。听起来就像一道给小学生练手的数数题。但等我把它搬到自家 OJ 上、看到"数据加强版"几个字之后，才发现这个"枚举算法"标签底下藏着的东西远比想象中多。题目本身非常朴素：给定一个 n×m 的矩形网格，问里面能数出多少个正方形、多少个长方形（非正方形矩形）。难点从来不在题目理解，而在你怎么数、用什么复杂度去数。这篇文章就从暴力枚举讲起，一路推到 O(1) 的纯公式解法，把数据加强版为什么能卡死一堆人这件事彻底说透。适合刚开始刷枚举专题的选手，也适合想把这类题迁移到 OJ 上的站长们参考。

1. 一道1997年的"数数题"，坑点到底在哪

1.1 正方形和长方形之间的定义边界

先看题目本身。给定一个 n 行 m 列的矩形网格，要求统计这个网格里的正方形个数，以及"长方形"的个数。注意这里的"长方形"是一个有特定口径的概念：它指的是非正方形的矩形。也就是说，所有四个角都是直角的四边形里，正方形单独归一类，剩下的宽高不相等的矩形才叫"长方形"。

这个定义坑了不少第一次做这道题的人。有人想当然地认为"长方形也包括正方形"，于是正方形数量统计得对，长方形数量却把正方形也算进去了，最后输出两个数之和等于矩形总数，其实统计口径已经错了。还有人手滑把正方形也算成矩形，导致两个答案加起来莫名其妙地大于总矩形数，怎么调都调不对。

正确的统计口径是：设 S 为正方形总数，R 为长方形总数，A 为所有矩形（包含正方形）的总数，那么应该满足：

A = S + R

也就是先数出所有矩形，再把正方形单独拿出来，剩下的就是非正方形矩形。

1.2 样例背后的计数逻辑

题目给的样例一般是 n=2、m=3 这样的组合。我们手动数一下：2×3 的方格子里，边长 1 的正方形有 2×3=6 个，边长 2 的正方形有 1×2=2 个，正方形一共 8 个。

所有矩形的数量呢？3 条横线和 4 条竖线，任意选两条横线、两条竖线就能确定一个矩形。总矩形数是：

C(3,2) × C(4,2) = 3 × 6 = 18

所以长方形数量等于 18 - 8 = 10 个。样例输出就是 8 和 10。

到这里题目逻辑已经清楚了，表面上就是一个"数数"的活。但真正的问题来了：n 和 m 能大到什么程度？原版数据范围很小，很多老题解用三重循环甚至四重循环都能过。数据加强版直接把范围拉到一个完全不同的量级，枚举的写法和枚举的思维就必须升级了。

1.3 数据加强版到底改了什么

老版本 P2241 的数据范围我记得是 n、m 不超过 100 左右，嵌套循环暴力数每个矩形完全可行。数据加强版把范围提到了 5000，这一下就把复杂度从"随便跑"变成了"必须算清楚账"。5000×5000 的网格，总共大约两千五百万个小格子，但矩形数量是组合级别的，远远不是格子数量能代表的。后面会详细算这一笔复杂度账，这里先记住一个结论：在加强版的数据范围下，四重循环枚举矩形是绝对跑不完的。

2. 从四重循环到二重循环：两种直观枚举写法

2.1 枚举左上角和右下角：最符合直觉但最慢的做法

很多人第一次写这道题，脑子里的第一反应是：枚举矩形的左上角和右下角，判断宽高是否相等。

for (int x1 = 0; x1 < n; x1++) { for (int y1 = 0; y1 < m; y1++) { for (int x2 = x1; x2 < n; x2++) { for (int y2 = y1; y2 < m; y2++) { int h = x2 - x1 + 1; int w = y2 - y1 + 1; if (h == w) square++; else rect++; } } } }

这四个循环非常直观，但它做的事情是枚举了网格里每一个具体的矩形。n=m=100 的时候，循环量大概是亿级别，勉强能跑；n=m=5000 的时候，循环次数直接飙到约 6.25×10^14 次，这在任何 OJ 上都是不可能通过的量级。

这也是数据加强版设计的精妙之处：它逼着你不能一个一个数矩形，必须找出批量计算的规律。暴力枚举在竞赛里不是不能用，但前提是你得先估算清楚自己枚举的量级。

2.2 枚举宽和高：从 O(n²m²) 降到 O(nm)

四重循环的浪费在于：它把矩形的位置和大小混在一起枚举了。实际上，一个矩形的特征可以拆成两个独立维度——它的大小（宽和高），以及它在网格里的位置。

对于宽为 w、高为 h 的矩形，它在 n 行网格里纵向可以放 n-h+1 个位置，横向可以放 m-w+1 个位置。所以只要枚举宽和高，然后用乘法算出位置数，就能一次性统计掉一大类矩形：

for (int h = 1; h <= n; h++) { for (int w = 1; w <= m; w++) { long long cnt = 1LL * (n - h + 1) * (m - w + 1); if (h == w) square += cnt; else rect += cnt; } }

这里 cnt 表示"高为 h、宽为 w 的矩形一共有多少个位置"，乘法理解起来很直观：纵向选一个起点，横向选一个起点，就唯一确定一个矩形。

这个做法的复杂度是 O(nm)。n=m=5000 时，循环次数是两千五百万，已经可以轻松通过了。从四重循环到二重循环，优化思路的核心是：不再枚举矩形的具体位置，而是枚举矩形的类别，再用组合数学批量计算位置数。

2.3 5000 这个数字意味着什么

为什么 O(nm) 能过而 O(n²m²) 不能过？因为现代 OJ 一秒大概能跑 10^8 次简单运算。n=m=5000 时：

• 四重循环：约 1/4 × 5000^4 ≈ 1.56×10^14 次，按每秒 10^8 算，需要约 18 天。
• 二重循环：约 2.5×10^7 次，连 0.1 秒都用不到。
• 一重循环：约 5000 次，基本是瞬间完成。

这个对比就是"枚举算法"的精髓：同样是枚举，枚举的粒度决定成败。四个维度枚举具体矩形，和两个维度枚举矩形类别，背后是同一个题目，性能却差了九个数量级。

3. 正方形计数与矩形总数的公式化推导

3.1 正方形：按边长分层求和

二重循环已经能过，但它还不是最优解。细心的读者会发现，二重循环里其实有一半是在重复做事——正方形只出现在 h=w 的对角线上。而正方形这部分，可以单独用一个公式算出来。

观察一下：边长 k 的正方形，纵向能放 n-k+1 个位置，横向能放 m-k+1 个位置，所以边长 k 的正方形数量是：

(n - k + 1) × (m - k + 1)

边长 k 的取值范围从 1 到 min(n,m)。把所有边长加起来，就是正方形总数：

S = Σ_{k=1}^{min(n,m)} (n-k+1)(m-k+1)

这个求和式就是经典的"按边长分层"统计法。它的意义在于把我们从一个一个数正方形，变成了"按大小批量数"，只需要一重循环就能完成。

拿 n=m=3 验证一下：k=1 时 3×3=9 个，k=2 时 2×2=4 个，k=3 时 1×1=1 个，总数 14 个。和穷举结果完全一致。

3.2 矩形总数：组合计数视角

矩形总数不用枚举，直接用组合数学计算。

一个矩形由四条边确定：两条水平边、两条竖直边。在 n 行网格里一共有 n+1 条水平线，任意选两条就是矩形的一条水平边界；在 m 列网格里一共有 m+1 条竖直线，任意选两条就是矩形的竖直边界。

所以总矩形数：

A = C(n+1, 2) × C(m+1, 2) = [n(n+1)/2] × [m(m+1)/2]

这个公式也可以用另一个角度理解：横向选两个不同位置作为左右边界，纵向选两个不同位置作为上下边界。它天然地包含了所有正方形——因为正方形也是矩形的一种。

3.3 长方形等于总数减正方形：为什么不会重复

前面定义过统计口径：长方形是非正方形矩形。那么用矩形总数减去正方形总数，得到的就是长方形数量。这个减法能直接成立，是因为"矩形集合"被分成了两个互不重叠的子集——正方形集合和非正方形矩形集合。两个集合的并集恰好是所有矩形。

有同学会担心：这样减会不会把某个矩形重复减掉？不会。正方形集合里的每一个元素都是矩形，非正方形矩形集合里的每一个元素也都是矩形，两个集合交集为空，并集全覆盖。所以：

R = A - S

逻辑上是严密的。

3.4 从一重循环到 O(1)：平方和公式收尾

一重循环已经很快了，但既然标题里写了"数据加强版"，总有人会想：能不能做到常数时间？

可以。把正方形求和公式展开：

S = Σ_{k=1}^{t} (n-k+1)(m-k+1)

其中 t = min(n,m)。令 a=n+1，b=m+1，则：

n-k+1 = a-k m-k+1 = b-k

乘积展开：

(a-k)(b-k) = ab - (a+b)k + k²

于是：

S = t·ab - (a+b)·t(t+1)/2 + t(t+1)(2t+1)/6

最后一项用到平方和公式 Σk² = t(t+1)(2t+1)/6。这样正方形数量、矩形总数、长方形数量全部可以在 O(1) 时间内算出来。

不过说实话，在 n、m ≤ 5000 的范围内，一重循环和 O(1) 公式的运行时间都是肉眼不可见的。纯公式的价值更多在于理解计数结构，以及应对那些把范围加大到 10^9 甚至更大、连一重循环都不给过的变种题。

4. 代码实现与防爆细节：long long 和边界条件

4.1 一重循环版完整代码

这是我在 OJ 上实际提交的版本，够短、够稳，适合作为标准题解。

#include <bits/stdc++.h> using namespace std; int main() { long long n, m; cin >> n >> m; long long square = 0; long long t = min(n, m); for (long long k = 1; k <= t; k++) { square += (n - k + 1) * (m - k + 1); } long long total = n * (n + 1) / 2 * m * (m + 1) / 2; long long rect = total - square; cout << square << " " << rect << endl; return 0; }

4.2 O(1) 纯公式版完整代码

如果想把常数压到底，或者应对超大范围，用这个版本：

#include <bits/stdc++.h> using namespace std; int main() { long long n, m; cin >> n >> m; long long t = min(n, m); long long a = n + 1, b = m + 1; long long square = t * a * b - (a + b) * t * (t + 1) / 2 + t * (t + 1) * (2 * t + 1) / 6; long long total = n * (n + 1) / 2 * m * (m + 1) / 2; long long rect = total - square; cout << square << " " << rect << endl; return 0; }

4.3 最容易翻车的三个细节

第一个细节是类型。n=m=5000 时，矩形总数约 1.56×10^14，早已超出 int 能表示的 21 亿。用 int 存答案，最后输出的是溢出后的错误结果，而且这种错误非常隐蔽，小数据全对，大数据全错。

第二个细节是乘法顺序。total 那一行，如果 n、m 是 int，n * (n + 1)这一步就可能溢出。所以要么把 n、m 直接声明成 long long，要么在乘法前显式强转。我见过不少人死在这一行：明明公式背得滚瓜烂熟，却因为 n、m 是 int，在 5000 的数据下直接溢出。

第三个细节是正方形求和循环的边界。一定要用 t = min(n,m) 作为上限。如果 n=m 倒无所谓，一旦 n 和 m 不相等，比如 n=5000、m=1，循环写成 k≤n 就会把 m-k+1 算成负数，得出完全错误的结果。

还有一个小技巧：一重循环里 square 累加时，(n-k+1)*(m-k+1) 在 n、m 是 long long 的情况下是安全的，但如果 n、m 是 int，依然需要强转成 long long。最稳妥的做法就是在读入时直接定义为 long long，一劳永逸。

5. 从这道题看枚举算法的边界思维

5.1 什么时候可以放心暴力

很多新手对枚举有一种误解，觉得"枚举就是暴力，暴力就是超时"。其实枚举是一种非常通用的思维框架，关键在于对枚举量和数据规模的预判。

有一个简单的经验法则：一秒钟之内，大约能跑 10^8 次简单运算。所以当你设计算法时，先算一下最坏情况下要枚举多少种状态。如果状态量在 10^6 到 10^7 这个量级，暴力枚举可以放心用；如果到 10^9 以上，就必须考虑优化；如果到 10^12 以上，基本只能靠数学公式了。

P2241 这道题把四重循环、二重循环、公式解三个层次的复杂度都体现得淋漓尽致。它就是一道非常适合训练"枚举思维"的题目：从枚举具体对象，到枚举类别，再到完全脱离枚举，每一步都有清晰可验证的递进。

5.2 枚举的优化方向：减少维度、合并同类项

这道题展示了两条通用的枚举优化路径。

第一条路径是减少枚举维度。四重循环枚举左上角和右下角，本质上是把"位置"和"大小"两个维度混在一起；二重循环只枚举宽和高，位置维度用乘法公式一步算掉。类似的优化在二维前缀和、区间计数等题目里非常常见。

第二条路径是合并同类项。正方形求和公式把 k 从 1 到 min(n,m) 的同类项合并成了一个算式，再用平方和公式消掉循环。这种"把循环变成公式"的思路，本质上是数学归纳法在竞赛算法中的直接应用。

5.3 迁移 OJ 时的测试点设计经验

最后说点题外话。如果你和我一样，是把这道题迁移到自家 OJ 上的站长，测试点设计一定要覆盖几个极限情况：

• n=1、m=1：只有 1 个正方形，0 个长方形。
• n=1、m=5000：一行长条，正方形有 5000 个，长方形为 0。很多人会在这里把正方形和长方形搞混。
• n=5000、m=5000：最大值，验证 long long 是否用对。
• n=2、m=3：经典样例，验证基础正确性。

尤其 n=1 或 m=1 的边界测试点，能揪出所有没有用 min(n,m) 做循环上限的代码。我实际迁移时发现，不少从网上抄来的题解在 n=1、m=5000 这种非方形数据下会输出负数，就是因为正方形求和循环多跑了几轮，把 (m-k+1) 算成了负数。数据加强版的意义不只是放大数字，更在于让这些隐藏在"正常数据"下的逻辑漏洞全部现形。

这大概就是老题新做的乐趣。一道 1997 年的普及组题，放到今天的数据范围下，依然能教给选手很多关于枚举深度和计数本质的东西，也能让 OJ 管理员在造数据时重新审视一遍自己的测试点设计。如果你正在刷枚举专题，这道题值得反复做三遍：第一遍用四重循环理解题意，第二遍用二重循环学会批量计数，第三遍推出 O(1) 公式再回看一遍代码——每过一个阶段，你看到的东西都会不一样。