昨天在洛谷刷题翻到 P2241 统计方形数据加强版。第一眼扫过去心想这不就是个二维计数题嘛棋盘上数正方形和长方形随便套两层循环就能过。结果真的动手写了才发现题目带“数据加强版”三个字坑远比想象中多。普通枚举在 n、m 小的时候还能糊弄过去数据一大就是 TLE 和 WA 轮着来。这篇文章我就把这题的完整推导思路、O(1) 公式、C / Java 实现、以及对拍调试技巧全部摊开聊。不绕弯子直接做分析。这道题非常适合正在刷普及组、准备冲提高组的同学尤其是遇到“组合计数”就喜欢硬枚举的人。看完之后你会发现这类棋盘计数题看起来是模拟题本质是数学题。给个提前避雷提示题目里说的“长方形”在不同平台有歧义洛谷这题明确是不包含正方形的。1. 先把题目读懂到底在数什么1.1 棋盘模型与两个关键定义题目给了我们一个 n 行 m 列的棋盘每个单元格是一个 1×1 的小方格。需要我们回答两个数这个棋盘里有多少个正方形有多少个长方形。听起来简单但要先统一口径长方形不包括正方形。这一点非常关键。如果你直接把“所有矩形”数量当成“长方形”数量交上去样例可能都能过但判分一定 WA。因为数学上长方形是“有一个角是直角的平行四边形”而正方形是“四边相等的矩形”属于矩形的特殊子集。但在信息学奥赛的题目语境里如果题目单独区分了“正方形”和“长方形”那这里的长方形就是“狭义的矩形”要手动把正方形减掉。所以这道题的本质是统计棋盘上所有矩形中有多少个正方形、多少个非正方形。这个“棋盘”我在做题时习惯把它看成由 (n1) × (m1) 个格点组成的网格而不是 n × m 个格子。这样想后面推导公式会顺很多。1.2 为什么“数据加强版”会卡人原始版本的 P2241 数据范围可能还比较温柔暴力四层循环也能跑。可一旦挂上“数据加强版”n、m 会变得很大暴力枚举所有矩形的思路直接报废。先算一笔账如果暴力枚举每个矩形的左上角坐标和右下角坐标左上角有 n×m 种选择右下角也有 n×m 种选择还要判断是否合法朴素复杂度是 O(n²m²)。当 nm100 时这就是一亿次操作勉强能压线当 nm1000 时就是一万亿次操作神仙难救。有人会想那我优化一下固定矩形的宽和高再统计每个尺寸有多少个位置。设宽为 w高为 h位置数就是 (n-h1)×(m-w1)总复杂度 O(n²)。这比 O(n²m²) 好多了但在数据加强版里依然不够稳。真正讲究的做法是用组合数学把问题化成 O(1) 的公式不管 n、m 多大一次运算直接出结果。1.3 从“数格子”到“数边线”的思维转变很多初学者卡在这道题上是因为一直在“数格子”而没有跳出来看“数边线”。要数一个矩形只要确定两条水平边和两条竖直边就行。在一个 n 行 m 列的棋盘里水平方向有 n1 条线竖直方向有 m1 条线。任意选两条水平线、两条竖直线就能确定唯一一个矩形。这就像在纸上画线段横坐标取两个点纵坐标取两个点围出来的四边形就是矩形。这个思路把所有矩形的总数直接从“一个一个枚举”变成了“组合数学”计算量立刻下降了好几个量级。这个思维转变是解题的核心也是很多计数类题目的通用套路。2. 正方形数量一个公式从枚举到 O(1)2.1 固定边长左上角就是突破口先算正方形。设正方形的边长为 k那么 k 的取值范围是从 1 到 min(n,m)。一个边长为 k 的正方形要想完全落在棋盘里它的左上角能放在哪些位置水平方向上左侧从 1 开始最右边能到 m-k1 列竖直方向上最上边能到 n-k1 行。所以边长为 k 的正方形数量就是 (n-k1)×(m-k1)。注意这里是乘起来不是加起来。为什么因为水平方向和竖直方向的选择是独立的先在上方选择一行放正方形的上边界有 n-k1 种再在左方选择一列放正方形的左边界有 m-k1 种两者组合出唯一的正方形位置。因此总的正方形数量S Σ_{k1}^{min(n,m)} (n-k1)(m-k1)这个公式已经比“枚举每个正方形”优雅多了复杂度 O(min(n,m))。说实话很多用 long long 的 AC 代码就是靠这个循环过的因为加强后的数据范围下这个循环依然能跑完。但我个人建议还是把它化成 O(1)后面讲原因。2.2 打表找规律正方形求和公式怎么来的先把上面这个和式化简。设 a min(n,m)b max(n,m)。这样处理后原本 n、m 谁大谁小都不影响结果。交换一下符号正方形数量变成S Σ_{k1}^{a} (b-k1)(a-k1)这个式子看着还是有点绕令 j a-k1它的取值就从 a 一直递减到 1。同时 b-k1 b - a j。代入后S Σ_{j1}^{a} j × (b-aj)拆开乘号S (b-a) × Σj Σj²到这里就用上了两个经典求和公式Σ_{j1}^{a} j a(a1)/2Σ_{j1}^{a} j² a(a1)(2a1)/6所以最终公式是S (b-a) × a(a1)/2 a(a1)(2a1)/6这个式子不仅好写而且完全避免了循环。比如 n2, m3则 a2, b3代入得 (3-2)×2×3/2 2×3×5/6 3 5 8。手算一下也确实是这样边长 1 的正方形有 2×36 个边长 2 的正方形有 1×22 个共 8 个没毛病。2.3 公式化简细节最小边和最大边怎么用有人会问为什么要用 a 和 b 而不是直接保留 n、m因为如果 n、m 大小不定直接展开会得到一个带有 min 和 max 的分段表达式写起来啰嗦还容易把符号写错。统一成 amin(n,m)、bmax(n,m) 后公式就是一个无分支的表达式。这个技巧在竞赛里非常常见。凡是遇到对称结构先判断大小再统一用较小值做循环边界或公式参数代码会简洁很多。而且这样的公式用的是加法、乘法和除法都是 O(1) 的完全不受数据范围影响。这里有个细节要注意如果你选择用循环来算正方形数量循环次数是 a min(n,m)而不是 max(n,m)。有的同学会想当然地循环到 n结果当 n 远大于 m 时后面全是 0 项白算一趟。虽然不至于 WA但是浪费时间而且容易让自己对公式结构产生错误理解。3. 矩形总数与“长方形”的减法思想3.1 任取两条横线、两条竖线现在算棋盘里所有矩形的总数。这一步用到的是我一直强调的“数边线”思想。棋盘竖直方向有 n1 条横线水平方向有 m1 条竖线。要确定一个矩形只要在 n1 条横线里选两条作为上边界和下边界再在 m1 条竖线里选两条作为左边界和右边界。所以所有矩形的总数是R C(n1, 2) × C(m1, 2)展开一下就是R [n(n1)/2] × [m(m1)/2]这个式子是不是看起来也很眼熟它本质上是“先选上下边、再选左右边”的两步组合。我最初做这题的时候还尝试过枚举所有矩形的左上角和右下角再判断是否合法结果把一个计数题做成了暴力模拟题复杂度完全没法看。换成组合数学之后代码量少了正确率也高了。3.2 计算总数后记得减掉正方形题目要求的长方形数量是“所有矩形减去正方形”的数量T R - S也就是说我们先把所有矩形算出来再扣掉其中是正方形的那些剩下的就是严格意义的长方形。这个减法思想特别重要它省去了单独分类讨论长方形的所有形态的麻烦。如果你不用这个思路而是直接去数长方形会遇到什么问题一个长方形可以由任意两条不平行的边构成但这并不是只要四条边不相等就行。在棋盘坐标系里长方形的位置、宽高组合很多直接枚举分类很容易漏掉斜着放的情况——虽然棋盘是正交网格只要四个角坐标直接确定的是标准正矩形不涉及旋转但分类讨论依然繁琐。用减法就不存在这个问题矩形总数是一个干净的组合数正方形数也是一个干净的和式两者相减就得到答案。3.3 手算验证小棋盘先跑一遍光说不练假把式拿一个 2×3 的小棋盘完整验证一遍。先算所有矩形总数R [2×3/2] × [3×4/2] 3 × 6 18再算正方形总数边长 1 的正方形有 2×3 6 个 边长 2 的正方形有 1×2 2 个S 6 2 8所以长方形数量是 18 - 8 10 个。你可以自己在纸上画一个 2 行 3 列的棋盘把所有矩形标出来数一数不是正方形的有几个最后一定是 10。这种用极小数验证公式的习惯能避免大量低级错误。我在做任何计数题时都会先构造一个能手算的小输入把公式结果和手算结果对上再提交到在线评测系统。4. 代码实现与数据加强版避坑指南4.1 C 参考代码与复杂度如果你想用最稳妥的方式实现我建议直接用 O(1) 的公式版本。代码如下#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); // 正方形数量O(1) 公式 long long square (b - a) * a * (a 1) / 2 a * (a 1) * (2 * a 1) / 6; // 所有矩形的数量 long long total n * (n 1) / 2 * (m * (m 1) / 2); // 长方形 所有矩形 - 正方形 long long rectangle total - square; cout square rectangle endl; return 0; }有人会担心先乘法后除法会不会溢出。其实这里我们做了个小优化n(n1)/2 这部分先算 n(n1) 再除以 2。在 n 和 n1 中必然有一个是偶数所以 n(n1) 一定可以被 2 整除直接整除不会丢精度。如果 n 很大更稳的写法是先把偶数拆出来除以 2 再乘另一个数但一般 long long 范围内这样写就够了。整个算法的时间复杂度是 O(1)空间复杂度是 O(1)。不管 n、m 多大都只需要几行算术。4.2 Java 实现洛谷刷题输入输出细节洛谷上有不少同学用 Java 刷题包括搜索热词里也有“java洛谷”。写 Java 版本时要注意一点用 Scanner 读入数据在数据量不大时没问题但 Java 的 System.out.println 输出两个数也很方便。这里给一个比较标准的写法import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); long n Long.parseLong(st.nextToken()); long m Long.parseLong(st.nextToken()); long a Math.min(n, m); long b Math.max(n, m); long square (b - a) * a * (a 1) / 2 a * (a 1) * (2 * a 1) / 6; long total n * (n 1) / 2 * (m * (m 1) / 2); long rectangle total - square; System.out.println(square rectangle); } }为什么用 BufferedReader 而不是 Scanner因为竞赛环境里如果赶上多组测试数据或者数据量偏大Scanner 的解析速度会成为瓶颈。本题只有一组输入Scanner 其实也没什么问题但养成用 BufferedReader 的习惯没坏处。另外就是所有参与计算的变量一律用 long千万不能用 int否则乘几个数就爆了。4.3 防溢出int 不够long long 可能也不够这题最容易翻车的点还不是算法而是溢出。如果 n、m 是 int 范围int 最大约 21 亿。n100000 时n(n1)/2 ≈ 5×10⁹已经超 int 了更不用说两个这样的数相乘。用 long long 后范围能到约 9.22×10¹⁸。官方加强版的数据范围用 long long 是能稳过的。但如果哪天题库把数据加强到 10⁹ 甚至更大那连 long long 都不够因为 n(n1)/2 大约 5×10¹⁷两者相乘就是 2.5×10³⁵远超 long long。遇到这种极端情况有三个方案第一是继续上 __int128GCC 编译器支持输出时需要手动转成字符串第二是直接用 Java 的 BigInteger第三是用 Python自带大整数丢给 Python 跑毫无压力。我在本地测试过用 Python 写这题几乎是白送分代码短不用考虑溢出但前提是你对 Python 的执行速度有预期。我的建议是竞赛前先确认题目的实际数据范围再决定用什么类型。如果数据范围描述不明确优先用 long long 配合公式写能过绝大多数情况。5. 常见错误与调试对拍心得5.1 错误行为速查表我整理了一个这题常见的错误表方便你提交前对照检查自己代码错误类型错误表现正确做法定义混淆把正方形算入长方形长方形 所有矩形 - 正方形枚举超时四重循环枚举矩形坐标用组合数学公式 O(1)整数溢出n、m 稍大就出负数或错误结果全部用 long long变量类型混用int 和 long long 相加统一转成 long long交换顺序出错输出正方形和长方形时搞反先输出正方形再输出长方形公式代入错误min、max 用反amin(n,m)bmax(n,m)忘记减正方形长方形数量输出成所有矩形数量记得 total - square边界测试缺失小数据对大数据 WA构造 n1、nm 等边界用例其中“输出顺序”这种坑最冤枉。洛谷题目要求先输出正方形数量再输出长方形数量。你要是下意识按“长方形、正方形”的顺序输出小样例可能也看不出问题但提交后会直接 WA。遇到输出格式相关的错误先检查输出顺序再去找逻辑问题能省不少时间。5.2 没有样例自己制造样例对拍很多同学在本地跑完题目给的样例输出正确就提交然后 WA 了才一脸懵。更好的做法是写一个暴力程序用于对拍。暴力程序逻辑简单但复杂度高适合 n、m 很小的情况公式程序是正式提交的版本。然后用随机数生成大量小棋盘数据两个程序分别跑比较输出是否一致。我通常这样写对拍脚本第一份代码是暴力枚举O(n²m²)只确保 n、m ≤ 20 时能跑完第二份代码是正式版本用公式计算写一个随机生成器每轮生成 n、m范围 1 到 30循环 1000 次比较两份代码的输出。一旦发现输出不一致立刻把这一组 n、m 打印出来用 1.3 小节里的手算方法去验证到底是公式写错了还是暴力枚举写错了。这样定位问题非常快。对拍可以说是竞赛刷题中性价比最高的调试手段比对着代码干瞪眼强多了。5.3 考场策略数学计算永远比暴力循环优选这题给我们的启示是看到计数题先想能不能用组合数学不要急着模拟。暴力枚举是兜底方案不是首选方案。尤其当题目名称里写着“数据加强版”时出题人大概率把暴力做法卡得死死的。如果你在考场上一下没推出 O(1) 公式退而求其次用 O(min(n,m)) 的循环也是好选择至少代码简单、不容易写错。然后在保证正确性的前提下去优化剩余部分。反过来不要为了追求复杂公式而在推导时出错那比用一个复杂但错误的公式更惨。实战中我还会先用小数据验证公式再提交大数据。比如 n1、m1显然正方形 1 个长方形 0 个n1、m5正方形就是 5 个长方形是 0 个因为 1×5 的棋盘里所有矩形都是 1×k 的“条”没有宽大于 1 的矩形所以非正方形矩形数量是 0。这些极端边界用例能立刻暴露公式里有没有方向性错误。最后再分享一个这题的扩展思考。如果把“棋盘”从二维换成三维也就是 n×m×p 的长方体问有多少个正方体、长方体公式会变成三层求和加组合数相乘。思路完全一样正方体按边长累计长方体用三维组合数。你可以顺着这个方向自己推一推推完你对“组合计数”这类题的理解会再上一个台阶。这题虽然只是普及/提高-难度但背后体现的数学思想非常典型值得反复揣摩。