【算法解析】n×m 网格中正方形与长方形数量的数学推导与高效计算（漫画解析）
【算法解析】n×m 网格中正方形与长方形数量的数学推导与高效计算
在算法竞赛和编程面试中，经常遇到一类经典问题：给定一个n × m n \times mn×m的方格棋盘，求其中包含多少个正方形、多少个长方形（不包含正方形）。本文将从原理出发，详细推导其数学公式，并提供两种实现方式的对比分析，最终给出最优解。
典型题目链接：P2241 统计方形（数据加强版）
一、问题理解
题目中的“n × m n \times mn×m方格”指的是由n nn行、m mm列单位小方格组成的矩形网格。我们需要统计：
- 所有可能的正方形区域（边长为 1, 2, …,min ( n , m ) \min(n, m)min(n,m)，且边与网格线对齐）；
- 所有可能的长方形区域（不含正方形），即矩形中长 ≠ 宽的部分。
注意：这里的“矩形”包括正方形，而“长方形”在本题语境下特指“非正方形的矩形”。
二、总矩形数的推导
任意一个矩形由其上下边界和左右边界唯一确定。在一个n × m n \times mn×m的网格中：
- 水平方向有n + 1 n+1n+1条横线，从中任选 2 条作为上下边界，共有n ( n + 1 ) 2 \frac{n(n+1)}{2}2n(n+1)种选法；
- 垂直方向有m + 1 m+1m+1条竖线，从中任选 2 条作为左右边界，共有m ( m + 1 ) 2 \frac{m(m+1)}{2}2m(m+1)种选法。
因此，所有矩形的总数为：
T = n ( n + 1 ) 2 ⋅ m ( m + 1 ) 2 T = \frac{n(n+1)}{2} \cdot \frac{m(m+1)}{2}T=2n(n+1)⋅2m(m+1)
该公式简洁且高效，是后续计算的基础。
漫画演示：
三、正方形数量的两种求法
方法一：枚举边长（循环法）
设正方形边长为k kk（1 ≤ k ≤ min ( n , m ) 1 \leq k \leq \min(n, m)1≤k≤min(n,m)），则其左上角可在( n − k + 1 ) × ( m − k + 1 ) (n - k + 1) \times (m - k + 1)(n−k+1)×(m−k+1)个位置放置。因此，正方形总数为：
S = ∑ k = 1 min ( n , m ) ( n − k + 1 ) ( m − k + 1 ) S = \sum_{k=1}^{\min(n,m)} (n - k + 1)(m - k + 1)S=k=1∑min(n,m)(n−k+1)(m−k+1)
该方法直观易懂，时间复杂度为O ( min ( n , m ) ) O(\min(n, m))O(min(n,m))。对于n , m ≤ 5000 n, m \leq 5000n,m≤5000的数据范围，最多执行 5000 次循环，在实际运行中完全可接受。
方法二：闭式公式（数学优化）
通过代数变换，上述求和可转化为闭式表达。令a = min ( n , m ) a = \min(n, m)a=min(n,m)，b = max ( n , m ) b = \max(n, m)b=max(n,m)，则：
S = ∑ k = 1 a ( a − k + 1 ) ( b − k + 1 ) = ∑ x = 1 a x ( b − a + x ) S = \sum_{k=1}^{a} (a - k + 1)(b - k + 1) = \sum_{x=1}^{a} x(b - a + x)S=k=1∑a(a−k+1)(b−k+1)=x=1∑ax(b−a+x)
令d = b − a d = b - ad=b−a，利用求和公式∑ x = a ( a + 1 ) 2 \sum x = \frac{a(a+1)}{2}∑x=2a(a+1)和∑ x 2 = a ( a + 1 ) ( 2 a + 1 ) 6 \sum x^2 = \frac{a(a+1)(2a+1)}{6}∑x2=6a(a+1)(2a+1)，可得：
S = d ⋅ a ( a + 1 ) 2 + a ( a + 1 ) ( 2 a + 1 ) 6 = a ( a + 1 ) ( 3 b − a + 1 ) 6 S = d \cdot \frac{a(a+1)}{2} + \frac{a(a+1)(2a+1)}{6} = \frac{a(a+1)(3b - a + 1)}{6}S=d⋅2a(a+1)+6a(a+1)(2a+1)=6a(a+1)(3b−a+1)
此即正方形数量的闭式公式，计算仅需常数时间。
验证示例
以n = 2 , m = 3 n = 2, m = 3n=2,m=3为例：
- a = 2 , b = 3 a = 2, b = 3a=2,b=3
- S = 2 ⋅ 3 ⋅ ( 9 − 2 + 1 ) 6 = 6 ⋅ 8 6 = 8 S = \frac{2 \cdot 3 \cdot (9 - 2 + 1)}{6} = \frac{6 \cdot 8}{6} = 8S=62⋅3⋅(9−2+1)=66⋅8=8
与手动枚举结果一致。
漫画演示：
四、长方形数量的计算
根据容斥原理：
长方形数量 = 总矩形数 − 正方形数量 = T − S \text{长方形数量} = \text{总矩形数} - \text{正方形数量} = T - S长方形数量=总矩形数−正方形数量=T−S
无需单独枚举非正方形矩形，避免了复杂的分类讨论。
五、代码实现对比
循环法（清晰直观）
longsquares=0;intmin=Math.min(n,m);for(intk=1;k<=min;k++){squares+=(long)(n-k+1)*(m-k+1);}闭式法（高效优雅）
longa=Math.min(n,m);longb=Math.max(n,m);longsquares=a*(a+1)*(3*b-a+1)/6;注意：所有变量必须使用
long类型，防止中间结果溢出。当n = m = 5000 n = m = 5000n=m=5000时，最大中间值约为2.5 × 10 11 2.5 \times 10^{11}2.5×1011，远超int范围（约2 × 10 9 2 \times 10^92×109）。
漫画演示：
六、效率与适用性分析
| 维度 | 循环法 | 闭式法 |
|---|---|---|
| 时间复杂度 | O ( min ( n , m ) ) O(\min(n, m))O(min(n,m)) | O ( 1 ) O(1)O(1) |
| 实际运行时间 | 微秒级（≤5000 次） | 纳秒级 |
| 代码长度 | 稍长 | 极简 |
| 可扩展性 | 仅适用于较小规模 | 适用于极大n , m n, mn,m（只要不超 long） |
| 通用性 | 仅适用于标准网格正方形计数 | 同左 |
虽然在本题数据范围内两者性能差异在 OJ 上可能都显示为 0ms，但闭式法体现了“用数学优化算法”的核心思想，是更优的工程实践。
七、公式的适用边界
该闭式公式仅适用于以下条件同时满足的情形：
- 网格完整无缺（无障碍物）；
- 正方形边必须与网格线平行（不允许旋转）；
- 统计所有尺寸的正方形总数。
若问题变体涉及障碍物、旋转正方形、仅统计特定边长、或三维扩展等，则需重新建模，不能直接套用此公式。
漫画演示：
八、总结
- 总矩形数：T = n ( n + 1 ) 2 ⋅ m ( m + 1 ) 2 \displaystyle T = \frac{n(n+1)}{2} \cdot \frac{m(m+1)}{2}T=2n(n+1)⋅2m(m+1)
- 正方形数：S = a ( a + 1 ) ( 3 b − a + 1 ) 6 \displaystyle S = \frac{a(a+1)(3b - a + 1)}{6}S=6a(a+1)(3b−a+1)，其中a = min ( n , m ) , b = max ( n , m ) a = \min(n,m), b = \max(n,m)a=min(n,m),b=max(n,m)
- 长方形数：T − S T - ST−S
推荐在实际编程中优先采用闭式公式法，它不仅效率更高，而且代码简洁、逻辑严谨，是解决此类组合计数问题的最佳实践。