洛谷P2241统计方形：从暴力枚举到组合数学公式的优化全解析

刷题群里有同学甩了道题过来，说“数据加强版”暴力写不动了，一看是洛谷 P2241 统计方形。这道题我印象挺深，属于那种“题目描述很简单，一看就会，一写就废”的典型。很多人第一反应是四重循环枚举矩形的两个顶点，或者三重循环枚举宽和高，提交后发现要么超时要么答案全是负数。数据加强版之后，n 和 m 的范围更大，暴力的路子直接被堵死，逼着你必须去把数学公式推出来。这篇就把这题的完整推导、几种写法和实际踩坑都捋一遍，适合刚接触算法竞赛、准备 CSP-J/S 或蓝桥杯的同学参考，思路搞懂了代码其实就几行。

1. 题目到底在问什么：先读懂“统计方形”

1.1 题意拆解与数据范围

洛谷 P2241 的题目描述很简单：给定一个 n 行 m 列的长方形网格，要求统计其中所有正方形和长方形的个数。这里有个关键点，题目说的“长方形”是不包含正方形的，也就是宽和高不相等的矩形才算长方形。输出格式是两行，第一行是正方形的个数，第二行是长方形的个数。

举个例子，一个 2 行 3 列的网格，也就是 n=2、m=3，里面正方形有几个？边长为 1 的有 2×3=6 个，边长为 2 的有 1×2=2 个，总共 8 个正方形。长方形有几个？把所有矩形数量算出来再减去正方形数量，答案是 10 个。这是这道题的基础理解。

“数据加强版”加强在哪？原版题目的 n、m 范围大概是 1 到 100 左右，暴力枚举勉强能跑。加强版直接把范围拉大，常见版本里 n、m 可以达到几千甚至上万。这时候如果还写四重循环，每重循环几百上千次，总操作量轻松破亿甚至千亿，在 OJ 上就是 TLE 的命运。就算优化成三重循环枚举宽高，再统计每种宽高下的数量，复杂度仍然是 O(n²m) 或 O(nm²)，数据一大依旧跑不动。

所以这道题本质上是考察两件事：一是能不能把“数图形”转换成数学公式，二是能不能意识到算法复杂度和数据范围之间的关系。这也是很多竞赛入门同学第一次接触“组合计数”思想的经典题目。

1.2 暴力思路为什么走不通

先说说新手最常见的暴力写法。网格里任意一个矩形可以由四个边界确定，也就是两条横线和两条竖线。所以可以枚举 top、bottom、left、right 四个位置，判断内部是否构成目标图形。这种写法复杂度是 O(n²m²)，n=m=100 时就是 1 亿次，按 OJ 一秒跑几亿次的水平勉强能过，但加强版把范围拉到 1000 以上，1 亿的 100 倍就是 100 亿次，直接超时。

还有人用三重循环：枚举矩形的高度 h 和宽度 w，然后数一数有多少个位置能放下这么高的矩形。对于一个 n 行 m 列的网格，高度为 h 的矩形在垂直方向上有 n-h+1 种放法，宽度为 w 的有 m-w+1 种放法，所以某种尺寸的矩形数量就是 (n-h+1)×(m-w+1)。再枚举所有 h、w 组合，复杂度是 O(nm)。这在原版能过，但加强版如果 n、m 都到 10000，nm 就是 1 亿，勉强能跑但不够优雅；再大一点比如 100000×100000，直接爆炸。

更重要的是，暴力的思路没有触及问题的本质。这类计数题考察的不是“数得快”，而是“找规律”。当你发现直接枚举太慢，就应该停下来想一想：能不能用排列组合的方式一次性算出来。

提示：看到“加强版”这种字眼，第一反应不是优化循环，而是换思路。数据范围扩大意味着原来依赖枚举的算法可能整体失效，需要 O(1) 或近似 O(1) 的方案。

2. 从“数格子”到“数线条”：核心推导

2.1 矩形总数：选两条横线两条竖线

要推导公式，得先换一个角度看网格。一个 n 行 m 列的网格，纵向有 n+1 条竖线（左右边界也算），横向有 m+1 条横线（上下边界也算）。网格里任意一个矩形，其实就对应着“从 n+1 条横线里选两条”和“从 m+1 条竖线里选两条”。这两组线条一交叉，就围成一个矩形。

这个结论很多人第一次听会觉得突然，但仔细想就能想通：矩形的上下边必定是两条不同的横线，左右边必定是两条不同的竖线。反过来，任意选两条横线和两条竖线，它们交叉形成的区域必然是一个矩形。所以矩形的总数就是：

• 横线的选法：C(n+1, 2) = n(n+1)/2
• 竖线的选法：C(m+1, 2) = m(m+1)/2
• 矩形总数 = n(n+1)/2 × m(m+1)/2

注意这里的矩形总数是包含正方形的，因为正方形也是矩形的一种。这个公式特别简洁，但它只能算出总数，算不出正方形和长方形的各自数量，所以接下来要单独求正方形。

这个思路也是整个题目的分水岭：一旦意识到“数矩形等价于选线”，复杂的循环就不需要了，公式两行搞定。理解了这一步，后面正方形个数的推导就顺理成章。

2.2 正方形个数：按边长分类计数

正方形有特殊性：它的宽和高必须相等。所以不能用“选两条横线两条竖线”直接套，因为这样选出来的四边不一定围成正方形。正确做法是按边长分类统计。

设正方形边长为 k，那么在一个 n 行 m 列的网格里，这个正方形在垂直方向上有 n-k+1 种放置位置，水平方向上有 m-k+1 种放置位置。例如 n=2、m=3、k=1 时，垂直方向 2 个位置，水平方向 3 个位置，共 6 个 1×1 正方形。为什么是 n-k+1？因为正方形占 k 行，网格共 n 行，它的上边界可以从第 1 行变化到第 n-k+1 行，一共 n-k+1 种选法。水平方向同理。

所以边长从 1 到 min(n, m) 的所有正方形数量就是：

S = Σ(k=1 到 min(n,m)) (n-k+1)(m-k+1)

这个求和公式写一个 for 循环就能算，复杂度 O(min(n,m))，加强版一般够用。不过如果数据再往上走，比如 n、m 达到 10⁷，循环也可能吃力，那就需要进一步推导成 O(1) 的闭合公式。

设 s = min(n, m)，d = |n - m|，不妨假设 n ≤ m，那么 m = n + d。代入求和式，令 i = n - k + 1，当 k=1 时 i=n，当 k=n 时 i=1，也就是 i 从 1 循环到 n：

S = Σ(i=1 到 n) i(i+d) = Σi² + dΣi = n(n+1)(2n+1)/6 + d·n(n+1)/2

这个公式就不依赖循环了，直接四则运算算出正方形个数。不过要注意的是，这个推导过程中用到的乘法可能很大，实际写代码时要小心溢出。

2.3 小范围手算验证：公式靠不靠谱跑一下就知道

光推导不验证容易出错，这里拿 n=2、m=3 手工算一遍，把每个尺寸的矩形都列出来，对比公式结果。

2 行 3 列的网格，所有可能的矩形尺寸及数量如下：

把所有数量加起来，矩形总数为 6+4+2+3+2+1=18。正方形是 6+2=8。长方形 18-8=10。

用公式验证：矩形总数 = 2×3/2 × 3×4/2 = 3×6 = 18。正方形总数 = 2×3+1×2 = 8。完全吻合。

这种手算验证的方法特别值得养成习惯。竞赛题里很多时候公式推了半天以为是对的，结果边界条件漏了或者符号写错，导致整题 WA。用小数据手工跑一遍，能过滤掉大部分低级错误。

3. 代码实现：从 O(N) 到 O(1)

3.1 最稳的 O(min(n,m)) 写法

理论推导完了，代码其实很简单。我个人推荐先写 O(min(n,m)) 的版本，因为代码直观、不容易推错公式，而且对绝大多数数据范围都够用。C++ 写法如下：

#include <iostream> #include <algorithm> using namespace std; int main() { long long n, m; cin >> n >> m; long long limit = min(n, m); long long square = 0; for (long long k = 1; k <= limit; k++) { square += (n - k + 1) * (m - k + 1); } long long total = n * (n + 1) / 2 * (m * (m + 1) / 2); long long rectangle = total - square; cout << square << endl; cout << rectangle << endl; return 0; }

这里有几个细节必须注意。第一，所有变量都要用 long long，不能用 int。这个点说起来轻松，但“数据加强版”最大的陷阱就在这里。n 和 m 范围一大，n(n+1)/2 这个值很容易超过 21 亿，int 直接溢出变成负数，后面再减去 square 还越减越乱，最终输出一坨莫名其妙的长整数。很多人提交 WA 后查了半天，最后发现就是 int 惹的祸。

第二，循环变量 k 也要用 long long。如果 n、m 是 int 而 k 是 int，那么 (n-k+1)*(m-k+1) 这个乘法会先按 int 计算再赋给 long long，同样会溢出。加强版数据下这是非常隐蔽的坑。

第三，关于 total 的计算，有人喜欢写成：

long long total = n * (n + 1) * m * (m + 1) / 4;

这种写法虽然数学上等价，但 n(n+1)m(m+1) 这个乘积会先算出来再除以 4，中间结果可能非常大。虽然 long long 能扛住的范围很大，但没必要冒险。先分别除以 2 再相乘，中间值更小、更安全。

3.2 Java 写法与输入输出性能

如果你用的是 Java，思路完全一样，但有几个 Java 特有的坑。先看代码：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long m = sc.nextLong(); long limit = Math.min(n, m); long square = 0; for (long k = 1; k <= limit; k++) { square += (n - k + 1) * (m - k + 1); } long total = n * (n + 1) / 2 * (m * (m + 1) / 2); long rectangle = total - square; System.out.println(square); System.out.println(rectangle); } }

Java 的 long 对应 C++ 的 long long，范围是 -9223372036854775808 到 9223372036854775807，这道题完全够用。但如果你用 int，就会出现和 C++ 一样的溢出问题。

输入输出方面，洛谷这类 OJ 对 Java 的时限往往比较紧。Scanner 虽然写起来省事，但在 n、m 很大的场景下，读两个数问题不大，但在有些题目里需要读多组数据时，Scanner 性能就会拖后腿。建议养成用 BufferedReader 的习惯：

import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); long n = Long.parseLong(st.nextToken()); long m = Long.parseLong(st.nextToken()); in.close(); long limit = Math.min(n, m); long square = 0; for (long k = 1; k <= limit; k++) { square += (n - k + 1) * (m - k + 1); } long total = n * (n + 1) / 2 * (m * (m + 1) / 2); long rectangle = total - square; System.out.println(square); System.out.println(rectangle); } }

这套模板在洛谷上跑 Java 题非常实用，多组数据的题也能顶得住。虽然是“统计方形”这种简单题目，但提前把这些基本功练好，后面做更复杂的题目时不会输在 IO 上。

3.3 O(1) 公式版本与适用场景

如果数据范围继续加码，比如 n、m 达到 10⁹，O(min(n,m)) 的循环也会超时。这时候就需要上闭合公式。前面已经推导过，这里直接给写法：

#include <iostream> #include <algorithm> using namespace std; int main() { long long n, m; cin >> n >> m; long long a = min(n, m); long long b = max(n, m); long long square = a * (a + 1) * (2 * a + 1) / 6 + (b - a) * a * (a + 1) / 2; long long total = n * (n + 1) / 2 * (m * (m + 1) / 2); long long rectangle = total - square; cout << square << endl; cout << rectangle << endl; return 0; }

这个版本把循环消掉了，只剩常数次运算。a(a+1)(2a+1)/6 是前 a 个自然数的平方和公式，后一项是 d 乘以前 a 个自然数的和，正好对应推导中的 Σi² 和 dΣi。a 是 min(n,m)，b 是 max(n,m)，两者差 d = b-a。

要注意，O(1) 版本虽然快，但中间过程有一个 a(a+1)(2a+1) 的乘法，如果 a 特别大（比如 10⁹），这个乘积是 10²⁷ 量级，long long 根本存不下。遇到这种极端数据，任何整数类型都会溢出，只能换 BigInteger 或者用更高级的数论处理方式。好在常规 OJ 题不会出到这种程度，long long 足够应对绝大多数场景。

实操心得：我个人的习惯是优先写 O(min(n,m)) 循环版本，因为公式版本推起来容易出错，一旦 a、b 搞反或者少一项，WA 了很难排查。只有当明确知道 n、m 的范围大到循环撑不住，才特意用闭合公式。比赛里“够用就好”是很重要的原则。

4. 常见问题与排查：我踩过的坑

4.1 int 溢出：加强版最大的坑

这道题几乎所有 WA 都死于 int 溢出。以 n=50000、m=50000 为例，矩形总数 = 50000×50001/2 × 50000×50001/2，后者是 1250025000²，约等于 1.56×10¹⁸，远超 int 上限 2147483647。如果你用 int 计算，得到的结果会变成一个负数，而 square 计算过程里每一项 (50000-k+1)×(50000-k+1) 也超过 int 范围，同样会溢出。

这里的根因是 C++ 和 Java 里整数运算会先按操作数中精度最高的类型进行，两个 int 相乘结果还是 int，等到赋给 long long 时已经晚了。必须从一开始就用 long long 声明变量，或者至少做一次类型转换：

long long square += 1LL * (n - k + 1) * (m - k + 1);

那个 1LL 强制把整个运算提升到 long long 域，是避免溢出最简单粗暴的方法。我刷题时遇到乘法就习惯性带上 1LL，已经形成了肌肉记忆。

怎么排查这种问题？如果提交后答案出现负数、小数点乱掉或者和样例差很多，十有八九是溢出。把代码里的 int 全换成 long long 再提交一次，往往瞬间从 WA 变 AC。

4.2 把“长方形”当成“所有矩形”

题目要求的“长方形”特指不包含正方形的矩形。很多人算矩形总数时用了组合公式 n(n+1)/2×m(m+1)/2，以为这就是长方形的数量，直接输出，提交后样例都过不了。题目里那个“长方形个数”需要先用总数减去正方形个数，输出 total - square。

这一点最容易错的地方在于读题不仔细。竞赛题里“矩形”“长方形”“正方形”三个词经常混用，但在这题里它们是并列关系：正方形属于矩形但不属于这里的“长方形”，长方形是扣掉正方形之后的部分。做题之前先把输出要求看清楚，别急着写代码。我见过不少人在本地跑样例发现输出多了一个数，回头读题才发现理解错了概念。

4.3 边界数据：n=1 或 m=1 时别慌

当 n=1、m=3 时，也就是一行三列的网格，正方形只有 3 个（边长 1 的），长方形有 0 个。用公式验证：正方形 S = Σ(1-k+1)(3-k+1) = k=1 时 1×3=3。矩形总数 = 1×2/2 × 3×4/2 = 1×6=6。长方形 = 6-3=3。

等等，这个结果对不上。一行三列的网格里，三个正方形分别是三个 1×1 的格子，但还有两个 1×2 的矩形和一个 1×3 的矩形呀，它们宽不等于高，应该算长方形，所以长方形应该是 3 个，不是 0 个。我刚才口算“长方形 0 个”是错的，重新想一下。

n=1、m=3 的网格：正方形只有 1×1 的，共 3 个。矩形（含正方形）按组合公式，横线 C(2,2)=1 种，竖线 C(4,2)=6 种，总共 6 个。其中正方形 3 个，长方形 6-3=3 个。没错，那 3 个长方形就是 1×2、1×2、1×3。我前面说 0 个是口误，实际用公式算出来是正确的。

这个例子说明边界数据考验的不是公式而是细心。n 和 m 哪个小哪个大无所谓，因为正方形公式里 min(n,m) 就是边长上限，如果一边长度为 1，那就只有边长 1 的正方形。循环和公式都能正确处理这种情况，只要别把 n、m 读反就行。

4.4 超时问题的排查顺序

如果提交后不是 WA 而是 TLE，排查顺序应该是：先看算法复杂度，再看循环写法，最后看 IO。这道题如果还在用四重循环，直接改成公式版；如果已经用了 O(min(n,m)) 还超时，那多半是 n、m 真的特别大，得用闭合公式。

C++ 的 cin/cout 默认同步并不慢到离谱，但如果没关同步，在大输入下可能成为瓶颈。建议在 main 开头加一句：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行能显著加快 C++ 的输入输出。Java 那边则建议用 BufferedReader，细节部分上一节已经写了。不过说实话，这道题的输入就两个数字，IO 怎么都不可能成为瓶颈，TLE 的根源几乎都在算法本身。

另外要留意平台有没有多组测试数据。洛谷的 P2241 是单组输入，但有些类似的题目会要求“输入多组数据，直到文件末尾”。如果题目描述里没有明确，最好先确认一下。多组输入时循环需要写成 while(cin>>n>>m)，否则只处理一组数据会 WA 到怀疑人生。

4.5 正确性和性能的双重保障：写题的小习惯

最后分享一个刷计数类题目很实用的小习惯：先用小数据暴力验证公式，再写优化代码。这个方法适用于所有“统计类”算法题，尤其是 P2241 这种公式可以手算验证的题目。

具体做法是，在本地写一个最暴力的双层或四层循环，对 n、m 从 1 到 10 的所有组合都跑一遍，算出暴力答案。然后用你写的公式代码跑同样的输入，对比两组输出是否完全一致。如果一致，说明推导或公式实现基本没问题，可以放心提交；如果不一致，根据具体哪一组数据出错，能很快定位是公式的问题还是边界处理的问题。

这个习惯听上去多花时间，实际上一劳永逸。我当初做这题时，先用 O(min) 循环版本对上暴力结果，再写闭合公式版本和循环版本对拍，整个过程不超过五分钟，但心里特别稳，一次 AC。

算法竞赛很多时候拼的不是手速，而是这种“先验证再提交”的耐心。尤其是加强版题目，数据范围一大，错误会被放大得很夸张，提前做好验证能省下大量调试时间。