【算法解析】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 n1n1条横线从中任选 2 条作为上下边界共有n ( n 1 ) 2 \frac{n(n1)}{2}2n(n1)种选法垂直方向有m 1 m1m1条竖线从中任选 2 条作为左右边界共有m ( m 1 ) 2 \frac{m(m1)}{2}2m(m1)种选法。因此所有矩形的总数为T n ( n 1 ) 2 ⋅ m ( m 1 ) 2 T \frac{n(n1)}{2} \cdot \frac{m(m1)}{2}T2n(n1)⋅2m(m1)该公式简洁且高效是后续计算的基础。漫画演示三、正方形数量的两种求法方法一枚举边长循环法设正方形边长为k kk1 ≤ 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−k1)×(m−k1)个位置放置。因此正方形总数为S ∑ k 1 min ( n , m ) ( n − k 1 ) ( m − k 1 ) S \sum_{k1}^{\min(n,m)} (n - k 1)(m - k 1)Sk1∑min(n,m)(n−k1)(m−k1)该方法直观易懂时间复杂度为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)amin(n,m)b max ( n , m ) b \max(n, m)bmax(n,m)则S ∑ k 1 a ( a − k 1 ) ( b − k 1 ) ∑ x 1 a x ( b − a x ) S \sum_{k1}^{a} (a - k 1)(b - k 1) \sum_{x1}^{a} x(b - a x)Sk1∑a(a−k1)(b−k1)x1∑ax(b−ax)令d b − a d b - adb−a利用求和公式∑ x a ( a 1 ) 2 \sum x \frac{a(a1)}{2}∑x2a(a1)和∑ x 2 a ( a 1 ) ( 2 a 1 ) 6 \sum x^2 \frac{a(a1)(2a1)}{6}∑x26a(a1)(2a1)可得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(a1)}{2} \frac{a(a1)(2a1)}{6} \frac{a(a1)(3b - a 1)}{6}Sd⋅2a(a1)6a(a1)(2a1)6a(a1)(3b−a1)此即正方形数量的闭式公式计算仅需常数时间。验证示例以n 2 , m 3 n 2, m 3n2,m3为例a 2 , b 3 a 2, b 3a2,b3S 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} 8S62⋅3⋅(9−21)66⋅88与手动枚举结果一致。漫画演示四、长方形数量的计算根据容斥原理长方形数量 总矩形数 − 正方形数量 T − S \text{长方形数量} \text{总矩形数} - \text{正方形数量} T - S长方形数量总矩形数−正方形数量T−S无需单独枚举非正方形矩形避免了复杂的分类讨论。五、代码实现对比循环法清晰直观longsquares0;intminMath.min(n,m);for(intk1;kmin;k){squares(long)(n-k1)*(m-k1);}闭式法高效优雅longaMath.min(n,m);longbMath.max(n,m);longsquaresa*(a1)*(3*b-a1)/6;注意所有变量必须使用long类型防止中间结果溢出。当n m 5000 n m 5000nm5000时最大中间值约为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(n1)}{2} \cdot \frac{m(m1)}{2}T2n(n1)⋅2m(m1)正方形数S a ( a 1 ) ( 3 b − a 1 ) 6 \displaystyle S \frac{a(a1)(3b - a 1)}{6}S6a(a1)(3b−a1)其中a min ( n , m ) , b max ( n , m ) a \min(n,m), b \max(n,m)amin(n,m),bmax(n,m)长方形数T − S T - ST−S推荐在实际编程中优先采用闭式公式法它不仅效率更高而且代码简洁、逻辑严谨是解决此类组合计数问题的最佳实践。