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