刷题群里有同学甩了道题过来说“数据加强版”暴力写不动了一看是洛谷 P2241 统计方形。这道题我印象挺深属于那种“题目描述很简单一看就会一写就废”的典型。很多人第一反应是四重循环枚举矩形的两个顶点或者三重循环枚举宽和高提交后发现要么超时要么答案全是负数。数据加强版之后n 和 m 的范围更大暴力的路子直接被堵死逼着你必须去把数学公式推出来。这篇就把这题的完整推导、几种写法和实际踩坑都捋一遍适合刚接触算法竞赛、准备 CSP-J/S 或蓝桥杯的同学参考思路搞懂了代码其实就几行。1. 题目到底在问什么先读懂“统计方形”1.1 题意拆解与数据范围洛谷 P2241 的题目描述很简单给定一个 n 行 m 列的长方形网格要求统计其中所有正方形和长方形的个数。这里有个关键点题目说的“长方形”是不包含正方形的也就是宽和高不相等的矩形才算长方形。输出格式是两行第一行是正方形的个数第二行是长方形的个数。举个例子一个 2 行 3 列的网格也就是 n2、m3里面正方形有几个边长为 1 的有 2×36 个边长为 2 的有 1×22 个总共 8 个正方形。长方形有几个把所有矩形数量算出来再减去正方形数量答案是 10 个。这是这道题的基础理解。“数据加强版”加强在哪原版题目的 n、m 范围大概是 1 到 100 左右暴力枚举勉强能跑。加强版直接把范围拉大常见版本里 n、m 可以达到几千甚至上万。这时候如果还写四重循环每重循环几百上千次总操作量轻松破亿甚至千亿在 OJ 上就是 TLE 的命运。就算优化成三重循环枚举宽高再统计每种宽高下的数量复杂度仍然是 O(n²m) 或 O(nm²)数据一大依旧跑不动。所以这道题本质上是考察两件事一是能不能把“数图形”转换成数学公式二是能不能意识到算法复杂度和数据范围之间的关系。这也是很多竞赛入门同学第一次接触“组合计数”思想的经典题目。1.2 暴力思路为什么走不通先说说新手最常见的暴力写法。网格里任意一个矩形可以由四个边界确定也就是两条横线和两条竖线。所以可以枚举 top、bottom、left、right 四个位置判断内部是否构成目标图形。这种写法复杂度是 O(n²m²)nm100 时就是 1 亿次按 OJ 一秒跑几亿次的水平勉强能过但加强版把范围拉到 1000 以上1 亿的 100 倍就是 100 亿次直接超时。还有人用三重循环枚举矩形的高度 h 和宽度 w然后数一数有多少个位置能放下这么高的矩形。对于一个 n 行 m 列的网格高度为 h 的矩形在垂直方向上有 n-h1 种放法宽度为 w 的有 m-w1 种放法所以某种尺寸的矩形数量就是 (n-h1)×(m-w1)。再枚举所有 h、w 组合复杂度是 O(nm)。这在原版能过但加强版如果 n、m 都到 10000nm 就是 1 亿勉强能跑但不够优雅再大一点比如 100000×100000直接爆炸。更重要的是暴力的思路没有触及问题的本质。这类计数题考察的不是“数得快”而是“找规律”。当你发现直接枚举太慢就应该停下来想一想能不能用排列组合的方式一次性算出来。提示看到“加强版”这种字眼第一反应不是优化循环而是换思路。数据范围扩大意味着原来依赖枚举的算法可能整体失效需要 O(1) 或近似 O(1) 的方案。2. 从“数格子”到“数线条”核心推导2.1 矩形总数选两条横线两条竖线要推导公式得先换一个角度看网格。一个 n 行 m 列的网格纵向有 n1 条竖线左右边界也算横向有 m1 条横线上下边界也算。网格里任意一个矩形其实就对应着“从 n1 条横线里选两条”和“从 m1 条竖线里选两条”。这两组线条一交叉就围成一个矩形。这个结论很多人第一次听会觉得突然但仔细想就能想通矩形的上下边必定是两条不同的横线左右边必定是两条不同的竖线。反过来任意选两条横线和两条竖线它们交叉形成的区域必然是一个矩形。所以矩形的总数就是横线的选法C(n1, 2) n(n1)/2竖线的选法C(m1, 2) m(m1)/2矩形总数 n(n1)/2 × m(m1)/2注意这里的矩形总数是包含正方形的因为正方形也是矩形的一种。这个公式特别简洁但它只能算出总数算不出正方形和长方形的各自数量所以接下来要单独求正方形。这个思路也是整个题目的分水岭一旦意识到“数矩形等价于选线”复杂的循环就不需要了公式两行搞定。理解了这一步后面正方形个数的推导就顺理成章。2.2 正方形个数按边长分类计数正方形有特殊性它的宽和高必须相等。所以不能用“选两条横线两条竖线”直接套因为这样选出来的四边不一定围成正方形。正确做法是按边长分类统计。设正方形边长为 k那么在一个 n 行 m 列的网格里这个正方形在垂直方向上有 n-k1 种放置位置水平方向上有 m-k1 种放置位置。例如 n2、m3、k1 时垂直方向 2 个位置水平方向 3 个位置共 6 个 1×1 正方形。为什么是 n-k1因为正方形占 k 行网格共 n 行它的上边界可以从第 1 行变化到第 n-k1 行一共 n-k1 种选法。水平方向同理。所以边长从 1 到 min(n, m) 的所有正方形数量就是S Σ(k1 到 min(n,m)) (n-k1)(m-k1)这个求和公式写一个 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当 k1 时 in当 kn 时 i1也就是 i 从 1 循环到 nS Σ(i1 到 n) i(id) Σi² dΣi n(n1)(2n1)/6 d·n(n1)/2这个公式就不依赖循环了直接四则运算算出正方形个数。不过要注意的是这个推导过程中用到的乘法可能很大实际写代码时要小心溢出。2.3 小范围手算验证公式靠不靠谱跑一下就知道光推导不验证容易出错这里拿 n2、m3 手工算一遍把每个尺寸的矩形都列出来对比公式结果。2 行 3 列的网格所有可能的矩形尺寸及数量如下高度宽度数量是正方形112×36是122×24否132×12否211×33否221×22是231×11否把所有数量加起来矩形总数为 64232118。正方形是 628。长方形 18-810。用公式验证矩形总数 2×3/2 × 3×4/2 3×6 18。正方形总数 2×31×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(n1)/2 这个值很容易超过 21 亿int 直接溢出变成负数后面再减去 square 还越减越乱最终输出一坨莫名其妙的长整数。很多人提交 WA 后查了半天最后发现就是 int 惹的祸。第二循环变量 k 也要用 long long。如果 n、m 是 int 而 k 是 int那么 (n-k1)*(m-k1) 这个乘法会先按 int 计算再赋给 long long同样会溢出。加强版数据下这是非常隐蔽的坑。第三关于 total 的计算有人喜欢写成long long total n * (n 1) * m * (m 1) / 4;这种写法虽然数学上等价但 n(n1)m(m1) 这个乘积会先算出来再除以 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(a1)(2a1)/6 是前 a 个自然数的平方和公式后一项是 d 乘以前 a 个自然数的和正好对应推导中的 Σi² 和 dΣi。a 是 min(n,m)b 是 max(n,m)两者差 d b-a。要注意O(1) 版本虽然快但中间过程有一个 a(a1)(2a1) 的乘法如果 a 特别大比如 10⁹这个乘积是 10²⁷ 量级long long 根本存不下。遇到这种极端数据任何整数类型都会溢出只能换 BigInteger 或者用更高级的数论处理方式。好在常规 OJ 题不会出到这种程度long long 足够应对绝大多数场景。实操心得我个人的习惯是优先写 O(min(n,m)) 循环版本因为公式版本推起来容易出错一旦 a、b 搞反或者少一项WA 了很难排查。只有当明确知道 n、m 的范围大到循环撑不住才特意用闭合公式。比赛里“够用就好”是很重要的原则。4. 常见问题与排查我踩过的坑4.1 int 溢出加强版最大的坑这道题几乎所有 WA 都死于 int 溢出。以 n50000、m50000 为例矩形总数 50000×50001/2 × 50000×50001/2后者是 1250025000²约等于 1.56×10¹⁸远超 int 上限 2147483647。如果你用 int 计算得到的结果会变成一个负数而 square 计算过程里每一项 (50000-k1)×(50000-k1) 也超过 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(n1)/2×m(m1)/2以为这就是长方形的数量直接输出提交后样例都过不了。题目里那个“长方形个数”需要先用总数减去正方形个数输出 total - square。这一点最容易错的地方在于读题不仔细。竞赛题里“矩形”“长方形”“正方形”三个词经常混用但在这题里它们是并列关系正方形属于矩形但不属于这里的“长方形”长方形是扣掉正方形之后的部分。做题之前先把输出要求看清楚别急着写代码。我见过不少人在本地跑样例发现输出多了一个数回头读题才发现理解错了概念。4.3 边界数据n1 或 m1 时别慌当 n1、m3 时也就是一行三列的网格正方形只有 3 个边长 1 的长方形有 0 个。用公式验证正方形 S Σ(1-k1)(3-k1) k1 时 1×33。矩形总数 1×2/2 × 3×4/2 1×66。长方形 6-33。等等这个结果对不上。一行三列的网格里三个正方形分别是三个 1×1 的格子但还有两个 1×2 的矩形和一个 1×3 的矩形呀它们宽不等于高应该算长方形所以长方形应该是 3 个不是 0 个。我刚才口算“长方形 0 个”是错的重新想一下。n1、m3 的网格正方形只有 1×1 的共 3 个。矩形含正方形按组合公式横线 C(2,2)1 种竖线 C(4,2)6 种总共 6 个。其中正方形 3 个长方形 6-33 个。没错那 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(cinnm)否则只处理一组数据会 WA 到怀疑人生。4.5 正确性和性能的双重保障写题的小习惯最后分享一个刷计数类题目很实用的小习惯先用小数据暴力验证公式再写优化代码。这个方法适用于所有“统计类”算法题尤其是 P2241 这种公式可以手算验证的题目。具体做法是在本地写一个最暴力的双层或四层循环对 n、m 从 1 到 10 的所有组合都跑一遍算出暴力答案。然后用你写的公式代码跑同样的输入对比两组输出是否完全一致。如果一致说明推导或公式实现基本没问题可以放心提交如果不一致根据具体哪一组数据出错能很快定位是公式的问题还是边界处理的问题。这个习惯听上去多花时间实际上一劳永逸。我当初做这题时先用 O(min) 循环版本对上暴力结果再写闭合公式版本和循环版本对拍整个过程不超过五分钟但心里特别稳一次 AC。算法竞赛很多时候拼的不是手速而是这种“先验证再提交”的耐心。尤其是加强版题目数据范围一大错误会被放大得很夸张提前做好验证能省下大量调试时间。
