1. 从一道计数题说起格点三角形到底在数什么第一次看到“honoka和格点三角形”这个题目名很多人会愣一下——honoka是谁其实这不重要重要的是后面那五个字格点三角形。所谓格点就是平面直角坐标系里横纵坐标都是整数的点比如(0,0)、(1,2)、(-3,5)这些。格点三角形就是三个顶点全都落在格点上的三角形。这道题的核心要求通常是这样的在一个 (n \times m) 的格点矩阵里也就是横坐标从1到n、纵坐标从1到m的所有整点统计面积为1的格点三角形有多少个。注意是面积为1不是面积为1/2。这个区别非常关键因为格点三角形的面积有个著名结论——要么是整数要么是半整数。面积为1的三角形意味着它的“底乘高”等于2这就把问题转化成了对底和高的整数拆分。为什么这道题值得单独拿出来讲因为它是一道典型的计数类问题考的不是什么高深算法而是你能不能把一个大问题拆成几个互不重叠的小情况然后用乘法原理和加法原理干净利落地算出来。很多人在比赛里栽跟头不是因为不会写代码而是因为分类的时候漏了情况、或者算重了。我见过太多人在这道题上WAWrong Answer好几次最后发现是某个边界条件没考虑。这篇文章适合谁看如果你正在学算法基础、准备算法竞赛或者单纯对组合计数感兴趣那这篇内容会对你有帮助。我会从最朴素的暴力思路讲起然后一步步推导出O(1)的公式解法中间会详细解释每一步“为什么这么分类”“为什么这么算不会重复”。代码部分我会用C给出完整实现但思路是语言无关的。先明确一下问题的完整描述避免歧义。通常这类题目的设定是给定两个正整数n和m考虑所有横坐标在[1, n]、纵坐标在[1, m]范围内的格点。从这些格点中任选三个不共线的点组成三角形问有多少个三角形的面积恰好等于1。n和m的范围可能到10^9甚至更大所以暴力枚举三个点肯定不行必须找数学规律。注意有些版本的题目会要求“面积为1”有些会要求“面积为1/2”还有的会限制“三角形不能有边平行于坐标轴”。这些细节会直接影响公式的推导读题时一定要逐字确认。本文以“面积为1”这个最常见设定为准来展开。2. 暴力思路与复杂度分析为什么不能直接枚举拿到题目最直接的想法就是三重循环枚举三个点然后判断面积是否等于1。假设n和m都是100格点总数就是10000个三重循环的复杂度是 (O((nm)^3))也就是 (10^{12}) 级别完全不可接受。即使优化到枚举两个点、第三个点用数学条件去判断复杂度也是 (O((nm)^2))对于10^9级别的n和m来说依然是天文数字。所以这道题的本质不是“搜索”而是“计数”。计数的核心思想是不要一个一个去数而是找到一类具有相同结构的三角形算出这类三角形的数量然后把所有类加起来。这就像数一个停车场里有多少辆车你不需要一辆一辆数而是按颜色分类——红色有多少辆、蓝色有多少辆加起来就是总数。那么面积为1的格点三角形有哪些“类”呢关键在于三角形的面积公式。对于格点三角形有一个非常好用的工具叫鞋带公式Shoelace Formula也叫高斯面积公式。给定三个点 ((x_1,y_1))、((x_2,y_2))、((x_3,y_3))面积的两倍等于[ |S| |x_1(y_2-y_3) x_2(y_3-y_1) x_3(y_1-y_2)| ]面积等于1意味着 (|S| 2)。这个绝对值里的表达式是一个整数所以问题变成了有多少组三个格点使得这个表达式的绝对值等于2。但直接从这个公式出发还是太抽象。更直观的做法是利用“底和高”的关系。三角形的面积 底 × 高 / 2。面积等于1意味着底 × 高 2。由于底和高都是正数可能的组合只有两种(底, 高) (1, 2) 或者 (2, 1)。这里说的“底”和“高”需要是某种整数度量——对于格点三角形如果我们选一条边作为底那么这条底的长度不一定是整数可能是无理数但底所在直线与第三个点之间的“格点距离”是有讲究的。实际上对于格点三角形有一个更精确的结论如果三角形的一条边是水平或垂直的那么这条边的长度是整数第三个点到这条边的垂直距离也是整数因为第三个点的坐标是整数而水平/垂直直线的方程很简单。这种情况下面积 底 × 高 / 2底和高都是整数面积等于1就要求底×高2。但如果三角形的三条边都不水平也不垂直呢这时候底和高的计算就复杂了。不过有一个好消息对于面积为1的格点三角形它一定可以找到一条水平边或者垂直边作为底。这个结论不是显然的但可以通过枚举小范围内的格点三角形来验证。更严谨地说面积为1的格点三角形其形状只有有限的几种可能我们可以把它们全部枚举出来。实操心得在比赛里遇到这种计数题如果一时推不出公式可以先写一个暴力程序在小范围比如n,m≤10内枚举所有三角形把结果打表出来然后观察规律。这个方法我用了很多次非常有效。打表不仅能帮你验证公式还能帮你发现一些边界情况。3. 核心分类讨论把三角形按“底边方向”拆开现在我们来正式分类。面积为1的格点三角形按照它是否有一条水平边或垂直边可以分成两大类。更准确地说我们可以按照“底边”的方向来分类。这里说的底边是指我们用来计算面积的那条边。3.1 水平底边的情况假设三角形有一条水平边两个端点分别是 ((x_1, y)) 和 ((x_2, y))其中 (x_1 x_2)。这条边的长度是 (x_2 - x_1)是一个正整数。第三个点是 ((x_3, y_3))其中 (y_3 \neq y)否则三点共线。这个三角形的面积等于[ \text{面积} \frac{(x_2 - x_1) \times |y_3 - y|}{2} ]面积等于1所以[ (x_2 - x_1) \times |y_3 - y| 2 ]由于 (x_2 - x_1) 和 (|y_3 - y|) 都是正整数可能的组合只有(x_2 - x_1 1) 且 (|y_3 - y| 2)(x_2 - x_1 2) 且 (|y_3 - y| 1)这两种情况分别对应“底为1、高为2”和“底为2、高为1”。对于第一种情况底为1、高为2水平边的两个端点是相邻的格点横坐标相差1。第三个点与水平边的垂直距离为2也就是 (y_3 y 2) 或 (y_3 y - 2)。注意第三个点的横坐标 (x_3) 可以是任意值只要它不在这条水平边上就行。但实际上如果 (x_3) 取某些值三角形可能会退化或者与其它情况重复。我们需要仔细处理。对于第二种情况底为2、高为1水平边的两个端点横坐标相差2第三个点与水平边的垂直距离为1。3.2 垂直底边的情况完全对称地如果三角形有一条垂直边两个端点是 ((x, y_1)) 和 ((x, y_2))其中 (y_1 y_2)。这条边的长度是 (y_2 - y_1)。第三个点是 ((x_3, y_3))其中 (x_3 \neq x)。面积等于[ \text{面积} \frac{(y_2 - y_1) \times |x_3 - x|}{2} ]同样面积等于1要求(y_2 - y_1 1) 且 (|x_3 - x| 2)(y_2 - y_1 2) 且 (|x_3 - x| 1)3.3 为什么不会有“斜边底”的情况有人可能会问有没有可能三角形的三条边都不水平也不垂直但面积仍然是1答案是对于格点三角形如果面积为1那么它一定有一条水平边或垂直边。这个结论的证明需要用到数论中的一些知识但我们可以直观理解面积为1意味着“底×高2”而底和高的乘积很小所以三角形的形状非常“扁”或非常“窄”这种形状的格点三角形必然有一条边是水平或垂直的。更严谨地说可以通过枚举所有面积为1的格点三角形来验证这个结论。在n和m足够大的情况下所有面积为1的格点三角形都可以归入上面四种情况水平底两种、垂直底两种。这个结论是这道题能够用O(1)公式解决的关键。注意这里有一个容易出错的地方——同一个三角形可能同时有水平边和垂直边直角三角形也可能有多条水平边不可能因为三角形最多一条水平边。但一个三角形可能既有水平边又有垂直边比如直角三角形。这种情况下我们在按水平底边统计时会算它一次按垂直底边统计时又会算它一次导致重复计数。所以必须仔细设计统计方案确保每个三角形只被算一次。4. 不重不漏的计数方案按“最长水平边”或“最长垂直边”归类为了避免重复计数我们需要给每个三角形指定一个唯一的“代表边”。一个自然的想法是如果三角形有水平边就按水平边来统计如果只有垂直边没有水平边就按垂直边来统计。但问题是一个三角形可能既有水平边又有垂直边直角三角形这时候按哪个统计更好的方案是按照三角形的“底边”来统计但底边的选择要有一个明确的规则。比如我们可以规定如果三角形有水平边就选水平边作为底边如果有多条水平边不可能就选最长的那条。如果三角形没有水平边但有垂直边就选垂直边作为底边。如果既没有水平边也没有垂直边那就不统计因为我们已经论证了这种情况不存在。但这个规则还是有点模糊。更清晰的做法是直接按照三角形的形状来分类。面积为1的格点三角形形状其实非常有限。我们可以把它们全部画出来然后逐一计数。让我换一个更系统的思路。考虑所有面积为1的格点三角形我们可以按照“水平跨度”和“垂直跨度”来分类。所谓水平跨度就是三角形三个顶点中最大横坐标与最小横坐标之差垂直跨度类似。对于面积为1的三角形水平跨度和垂直跨度都不会太大。实际上通过枚举可以发现面积为1的格点三角形其水平跨度和垂直跨度最多为2。也就是说三角形的三个顶点都落在一个3×3的格点窗口内可能更小。这个观察极大地简化了问题我们只需要考虑那些“紧凑”的三角形。基于这个观察我们可以直接枚举所有可能的“形状”然后计算每种形状在n×m的格点矩阵中能放置多少个位置。这就是所谓的“模板法”。4.1 枚举所有可能的形状让我们在纸上画一画。面积为1的格点三角形可能的样子有类型一底为1、高为2的水平底三角形水平边的两个端点相邻比如(0,0)和(1,0)。第三个点的纵坐标与水平边相差2即y2或y-2。第三个点的横坐标可以是任意整数但为了不使三角形退化它不能使得三角形变成另一种已经统计过的形状。实际上如果第三个点的横坐标取0或1那么三角形会有一条垂直边。比如(0,0)、(1,0)、(0,2)这个三角形有水平边(0,0)-(1,0)也有垂直边(0,0)-(0,2)。如果我们按水平边统计它会被算一次如果按垂直边统计又会被算一次。所以我们需要决定这种“L形”的直角三角形到底归到哪一类一个简单的解决方案是只统计那些没有垂直边的水平底三角形。也就是说第三个点的横坐标不能与水平边的任一端点相同。这样水平底三角形和垂直底三角形就互不重叠了。但这样会不会漏掉一些三角形比如(0,0)、(1,0)、(0,2)这个三角形它既有水平边又有垂直边。如果我们规定“有水平边就按水平边统计”那么它会被算在水平底三角形里。但它的第三个点横坐标与端点相同如果我们排除这种情况就会漏掉它。所以我们需要更仔细地处理。其实最干净的方法是按照三角形的最长边来分类。但最长边可能不是水平或垂直的这就麻烦了。让我换一个角度。与其纠结于如何分类不如直接计算所有面积为1的三角形然后减去重复计算的。但这样更复杂。经过反复思考我发现一个更简单的方案分别计算“水平底”和“垂直底”的三角形数量然后减去“既是水平底又是垂直底”的三角形数量即直角三角形。这样就能保证不重不漏。具体来说设 (H) 为所有“有一条水平边且面积为1”的三角形数量不管它是否还有垂直边。设 (V) 为所有“有一条垂直边且面积为1”的三角形数量。设 (B) 为所有“既有水平边又有垂直边且面积为1”的三角形数量即直角三角形两条直角边分别水平垂直。那么总数量 (H V - B)。这个公式的原理是容斥原理(H) 和 (V) 的并集就是所有面积为1的三角形因为我们之前论证了每个面积为1的格点三角形至少有一条水平边或垂直边。(B) 是它们的交集。现在问题转化为分别计算 (H)、(V)、(B)。4.2 计算H水平底三角形的数量水平底三角形有两种子类型子类型H1底为1、高为2水平边的两个端点相邻横坐标相差1。在n×m的格点矩阵中水平边的选择方式对于每一行共m行有n-1条相邻的水平边。所以水平边的总数是 (m \times (n-1))。对于每条水平边第三个点需要与这条边垂直距离为2。也就是说第三个点的纵坐标是水平边所在行的上方2行或下方2行。上方2行要求水平边所在行 ≤ m-2下方2行要求水平边所在行 ≥ 3。第三个点的横坐标可以是任意值1到n但有一个限制如果第三个点的横坐标恰好等于水平边的某个端点的横坐标那么这个三角形会有一条垂直边它会被算在 (B) 里。但我们现在计算的是 (H)它包含了这些三角形。所以暂时不需要排除。不过还有一个问题如果第三个点的横坐标取某些值三角形可能会退化不会因为第三个点的纵坐标与水平边不同所以三点不共线。所以对于每条水平边第三个点的选择数是(n)横坐标任意× 2上方或下方如果存在的话。但要注意上方和下方不一定都存在。如果水平边在第1行或第2行上方2行可能不存在如果在第m行或第m-1行下方2行可能不存在。更精确地说对于一条在第r行的水平边上方2行存在当且仅当 (r 2 \leq m)即 (r \leq m-2)。下方2行存在当且仅当 (r - 2 \geq 1)即 (r \geq 3)。所以对于第r行可选的第三个点纵坐标有(r2)如果 (r \leq m-2)和 (r-2)如果 (r \geq 3)。数量为如果 (3 \leq r \leq m-2)2个选择。如果 (r 1) 或 (r 2)只有下方不对r1时下方2行是-1不存在上方2行是3如果m≥3则存在。所以r1时只有上方1个选择如果m≥3。r2时上方4存在如果m≥4下方0不存在。等等我需要重新理清。让我用更简单的方法对于每一行r第三个点的纵坐标可以是r2或r-2只要它们在1到m之间。所以对于第r行可选的纵坐标数量是[ c(r) [r2 \leq m] [r-2 \geq 1] ]其中 ([P]) 是艾弗森括号P为真时值为1否则为0。那么对于第r行水平边的数量是 (n-1)因为每行有n-1条相邻的水平边。每条水平边对应 (c(r) \times n) 个第三个点的选择横坐标任意纵坐标有c(r)种。所以[ H_1 (n-1) \times n \times \sum_{r1}^{m} c(r) ]其中 (\sum_{r1}^{m} c(r)) 是所有行中可选的纵坐标总数。计算 (\sum_{r1}^{m} c(r))对于r1c(1) [3≤m] [−1≥1] [m≥3] 0 [m≥3]。对于r2c(2) [4≤m] [0≥1] [m≥4]。对于r3到m-2c(r) 2如果m≥5。对于rm-1c(m-1) [m1≤m] [m-3≥1] 0 [m≥4] [m≥4]。对于rmc(m) [m2≤m] [m-2≥1] 0 [m≥3] [m≥3]。这个求和有点繁琐但可以化简。实际上我们可以换个角度所有可能的(水平边, 第三个点)组合等价于选择一条水平边和一条与之平行且距离为2的直线上的一个点。更简单的方法考虑所有可能的“底边高”的组合。水平边有 (m(n-1)) 条。对于每条水平边第三个点的纵坐标有c(r)种选择横坐标有n种选择。所以 (H_1 n \times \sum_{r1}^{m} (n-1) \times c(r) n(n-1) \sum_{r1}^{m} c(r))。而 (\sum_{r1}^{m} c(r)) 实际上等于所有满足 (|r - r| 2) 的有序对 (r, r) 的数量其中 r 是水平边的行r 是第三个点的行。对于每一对 (r, r)有 (n-1) 条水平边和 n 个横坐标选择。所以 (H_1 n(n-1) \times (\text{满足}|r-r|2\text{的有序对数量}))。满足 (|r-r|2) 的有序对 (r, r) 数量对于r从1到mr可以是r2或r-2。所以总数是 (2(m-2))因为r2≤m的有m-2个r-2≥1的有m-2个总共2(m-2)。因此[ H_1 n(n-1) \times 2(m-2) ]这个公式在m≥3时成立。如果m3则 (H_1 0)。子类型H2底为2、高为1水平边的两个端点横坐标相差2。在每一行有n-2条这样的水平边如果n≥3。水平边的总数是 (m(n-2))。第三个点与水平边的垂直距离为1即纵坐标为r1或r-1。类似地对于每一行r可选的纵坐标数量是[ d(r) [r1 \leq m] [r-1 \geq 1] ]对于r1d(1) [2≤m] 0 [m≥2]。 对于rmd(m) 0 [m-1≥1] [m≥2]。 对于2≤r≤m-1d(r) 2。所以 (\sum_{r1}^{m} d(r) 2(m-1))当m≥2时。因此[ H_2 n \times m(n-2) \times \frac{\sum d(r)}{m} ]不对让我重新算。对于每一行r水平边有n-2条。每条水平边对应 (d(r) \times n) 个第三个点选择横坐标任意纵坐标有d(r)种。所以[ H_2 (n-2) \times n \times \sum_{r1}^{m} d(r) n(n-2) \times 2(m-1) ]当m≥2时成立。所以[ H H_1 H_2 2n(n-1)(m-2) 2n(n-2)(m-1) ]这个公式在n≥3且m≥3时成立。如果n或m太小需要特殊处理。4.3 计算V垂直底三角形的数量完全对称地垂直底三角形也有两种子类型子类型V1底为1、高为2垂直边的两个端点相邻纵坐标相差1。在每一列有m-1条相邻的垂直边。垂直边的总数是 (n(m-1))。第三个点与垂直边的水平距离为2即横坐标为c2或c-2。类似地[ V_1 m(m-1) \times 2(n-2) ]子类型V2底为2、高为1垂直边的两个端点纵坐标相差2。在每一列有m-2条这样的垂直边。垂直边的总数是 (n(m-2))。第三个点与垂直边的水平距离为1[ V_2 m(m-2) \times 2(n-1) ]所以[ V V_1 V_2 2m(m-1)(n-2) 2m(m-2)(n-1) ]4.4 计算B直角三角形的数量直角三角形既有水平边又有垂直边。对于面积为1的直角三角形两条直角边的长度乘积必须为2。可能的组合水平边为1、垂直边为2水平边为2、垂直边为1情况B1水平边为1、垂直边为2直角顶点是两条直角边的交点。水平边从直角顶点延伸1个单位垂直边从直角顶点延伸2个单位。在n×m的格点矩阵中直角顶点的位置有 ((n-1)(m-2)) 种因为水平边需要右边有空间垂直边需要上方或下方有2个单位的空间。等等更准确地说直角顶点在(c, r)水平边的另一个端点在(c1, r)或(c-1, r)垂直边的另一个端点在(c, r2)或(c, r-2)。所以对于每个直角顶点有2种水平方向左或右× 2种垂直方向上或下 4种选择。但需要满足边界条件。实际上我们可以这样算水平边为1意味着直角顶点和水平边的另一个端点相邻。垂直边为2意味着直角顶点和垂直边的另一个端点纵坐标相差2。对于每个可能的直角顶点(c, r)水平方向c1≤n 或 c-1≥1所以有 ([cn] [c1]) 种选择。垂直方向r2≤m 或 r-2≥1所以有 ([r≤m-2] [r≥3]) 种选择。所以B1的总数是[ B_1 \sum_{c1}^{n} \sum_{r1}^{m} ([cn] [c1]) \times ([r≤m-2] [r≥3]) ]这个求和可以化简。(\sum_{c1}^{n} ([cn] [c1]) (n-1) (n-1) 2(n-1))。(\sum_{r1}^{m} ([r≤m-2] [r≥3]) (m-2) (m-2) 2(m-2))当m≥3时。所以[ B_1 2(n-1) \times 2(m-2) 4(n-1)(m-2) ]情况B2水平边为2、垂直边为1类似地[ B_2 4(n-2)(m-1) ]所以[ B B_1 B_2 4(n-1)(m-2) 4(n-2)(m-1) ]4.5 最终公式总数量 (H V - B)代入[ H 2n(n-1)(m-2) 2n(n-2)(m-1) ][ V 2m(m-1)(n-2) 2m(m-2)(n-1) ][ B 4(n-1)(m-2) 4(n-2)(m-1) ]所以[ \text{Total} 2n(n-1)(m-2) 2n(n-2)(m-1) 2m(m-1)(n-2) 2m(m-2)(n-1) - 4(n-1)(m-2) - 4(n-2)(m-1) ]这个公式看起来有点长但每一项都有明确的几何意义。我们可以进一步化简但保留这个形式更便于理解。实操心得在比赛里我建议先把公式写成这种“分项”的形式然后逐项验证。比如当n3, m3时手动枚举所有面积为1的三角形看看数量是否与公式一致。这种小范围验证能帮你快速发现公式中的错误。5. 代码实现与边界处理现在我们把公式翻译成代码。由于n和m可能很大比如10^9结果可能超出32位整数范围所以要用64位整数long long。#include iostream using namespace std; typedef long long ll; ll solve(ll n, ll m) { if (n 2 || m 2) return 0; // 无法构成面积为1的三角形 ll H1 2 * n * (n - 1) * (m - 2); ll H2 2 * n * (n - 2) * (m - 1); ll V1 2 * m * (m - 1) * (n - 2); ll V2 2 * m * (m - 2) * (n - 1); ll B1 4 * (n - 1) * (m - 2); ll B2 4 * (n - 2) * (m - 1); // 处理n或m小于3的情况此时某些项可能为负 if (n 3) { H2 0; V1 0; V2 0; B2 0; } if (m 3) { H1 0; H2 0; V2 0; B1 0; } ll total H1 H2 V1 V2 - B1 - B2; return total; } int main() { ll n, m; cin n m; cout solve(n, m) endl; return 0; }这段代码有几个需要注意的地方第一当n或m小于3时某些项会变成负数因为出现了(n-2)或(m-2)这样的因子。比如n2时n-20H20这没问题但V1中有(n-2)因子也会变成0。但如果n1n-2-1就会出现负数。所以我们需要在n3时把相关项置零。第二公式中的乘法可能会溢出。即使n和m在10^9以内n*(n-1)*(m-2)这样的乘积可能达到10^27级别远超long long的范围约9×10^18。所以如果题目中n和m很大需要在乘法过程中取模或者使用大数运算。但通常这类题目会要求结果对某个数取模比如10^97。如果题目没有要求取模那n和m的范围应该不会太大。第三边界情况n1或m1时格点退化成一条线无法构成三角形返回0。n2且m2时只有4个格点任选3个组成三角形面积最大为0.5比如(1,1),(2,1),(1,2)面积为0.5所以面积为1的三角形数量为0。我们的公式在n2,m2时H122100H222010V122100V222010B14100B24010总数为0正确。注意在实际比赛中如果n和m的范围达到10^9而结果没有要求取模那说明结果本身不会太大这不太可能。更常见的是要求对10^97取模。这时候需要在每一步乘法后取模并且减法时要加上模数再取模避免负数。6. 常见错误与排查技巧这道题虽然思路清晰但在实际编码中很容易出错。我整理了几个常见的坑错误一重复计数最常见的错误就是没有处理好直角三角形。如果直接计算HV而不减去B结果会偏大。我见过有人把H和V直接相加然后发现答案比预期大很多就是因为直角三角形被算了两次。错误二边界条件处理不当当n或m较小时某些项会变成负数。比如n2时H2中的(n-2)因子为0这没问题但V1中的(n-2)因子也为0V2中的(n-1)因子为1但V2还有(m-2)因子如果m≥3V2可能不为0。但实际上n2时格点只有两列垂直底三角形的第三个点需要水平距离为1或2但只有两列水平距离最大为1所以V2应该为0。我们的公式中V2 2m(m-2)(n-1)当n2时n-11V2 2m(m-2)这不为0这说明我们的公式在n2时有问题。让我重新检查V2的推导。V2是垂直底为2、高为1的情况。垂直边的两个端点纵坐标相差2第三个点与垂直边的水平距离为1。当n2时只有两列水平距离为1意味着第三个点必须在相邻的列。但垂直边本身占了一列第三个点在另一列这是可能的。比如垂直边在列1从(1,1)到(1,3)第三个点在列2纵坐标可以是2与垂直边的中点同高这样三角形(1,1),(1,3),(2,2)的面积为1。所以n2时确实存在这样的三角形。那么V2的公式在n2时应该是多少垂直边在列1有m-2条纵坐标从1到m-2。第三个点在列2纵坐标可以是垂直边两个端点之间的任意整数不对高为1意味着第三个点到垂直边的水平距离为1但垂直距离即第三个点的纵坐标与垂直边的“底”的垂直距离需要仔细定义。实际上对于垂直底为2、高为1的情况垂直边的两个端点纵坐标相差2第三个点的横坐标与垂直边相差1。第三个点的纵坐标可以是任意值吗不是因为面积 底 × 高 / 2 2 × 1 / 2 1。这里的高是第三个点到垂直边所在直线的水平距离即1。但垂直边所在直线是xc第三个点在xc±1。面积 (垂直边长度) × (水平距离) / 2 2 × 1 / 2 1。这个计算与第三个点的纵坐标无关也就是说第三个点的纵坐标可以是任意值只要它不与垂直边的端点重合导致退化。等等如果第三个点的纵坐标恰好等于垂直边的某个端点的纵坐标三角形会退化吗不会因为第三个点的横坐标不同所以三点不共线。比如垂直边(1,1)-(1,3)第三个点(2,1)这三点构成三角形面积为1底为2高为1。所以第三个点的纵坐标可以是1到m之间的任意值。但这样会不会导致重复计数比如垂直边(1,1)-(1,3)和第三个点(2,1)这个三角形也有水平边(1,1)-(2,1)吗(1,1)和(2,1)是水平边长度为1。这个三角形有水平边所以它也会被算在H里。这就是为什么我们需要减去B。所以V2的公式应该是垂直边有n(m-2)条每列m-2条共n列。对于每条垂直边第三个点的横坐标有2种选择左或右如果存在纵坐标有m种选择任意。所以V2 n(m-2) × 2 × m 2nm(m-2)。但这样算的话当n2时V2 22m*(m-2) 4m(m-2)这比之前的公式2m(m-2)(n-1) 2m(m-2)大了一倍。问题出在哪里问题在于当第三个点的纵坐标取某些值时三角形可能没有垂直边不垂直边是固定的三角形一定有这条垂直边。所以V2应该包含所有以这条垂直边为底的三角形。但等等如果第三个点的纵坐标恰好等于垂直边的某个端点的纵坐标那么这个三角形也有水平边。比如垂直边(1,1)-(1,3)第三个点(2,1)这个三角形有水平边(1,1)-(2,1)。所以它会被算在H里也会被算在V里最后减去B时会被减掉一次。这是正确的。所以V2的公式应该是垂直边有n(m-2)条每条垂直边对应2种水平方向如果存在× m种纵坐标选择。但水平方向的存在性取决于垂直边所在的列。如果垂直边在第1列只能向右在第n列只能向左在中间列可以向左或向右。所以V2 (m-2) × [2(n-2) 2] × m不对让我重新算。对于每一列c垂直边有m-2条。第三个点的水平方向如果c1只能向右1种如果cn只能向左1种如果1cn可以向左或向右2种。所以对于第c列第三个点的水平选择数 [c1] [cn]。总水平选择数 (\sum_{c1}^{n} ([c1] [cn]) (n-1) (n-1) 2(n-1))。所以V2 (m-2) × 2(n-1) × m 2m(m-2)(n-1)。这个公式在n2时给出V2 2m(m-2)(1) 2m(m-2)。但n2时总水平选择数 (2-1)(2-1) 2所以V2 (m-2) × 2 × m 2m(m-2)。这与公式一致。但之前我说n2时V2应该为0那是错误的。n2时确实存在垂直底为2、高为1的三角形。比如(1,1),(1,3),(2,2)面积为1。所以V2不为0。那么为什么我之前认为n2时V2应该为0因为我误以为水平距离为1意味着第三个点必须在相邻列而n2时只有两列垂直边占一列第三个点在另一列这是可能的。所以V2在n2时不为0。那么n2时总数量是多少让我们手动枚举n2, m3的情况。格点有(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)共6个点。任选3个组成三角形面积为1的有哪些(1,1),(1,3),(2,2)面积 |1*(3-2) 1*(2-1) 2*(1-3)|/2 |11 11 2*(-2)|/2 |11-4|/2 2/2 1。✓(1,1),(2,1),(2,3)面积 |1*(1-3) 2*(3-1) 2*(1-1)|/2 |-240|/2 1。✓(1,3),(2,3),(2,1)面积 |1*(3-1) 2*(1-3) 2*(3-3)|/2 |2-40|/2 1。✓(1,2),(2,2),(1,1)面积 |1*(2-1) 2*(1-2) 1*(2-2)|/2 |1-20|/2 0.5。✗(1,1),(1,2),(2,3)面积 |1*(2-3) 1*(3-1) 2*(1-2)|/2 |-12-2|/2 0.5。✗所以n2, m3时面积为1的三角形有3个。用我们的公式n2, m3。H1 221*(3-2) 4 H2 220*(3-1) 0 V1 232*(2-2) 0 V2 231*(2-1) 6 B1 41(3-2) 4 B2 40(3-1) 0Total 4 0 0 6 - 4 - 0 6。但手动枚举只有3个这说明公式有问题。让我重新检查H1的计算。n2, m3时H1是水平底为1、高为2的三角形。水平边有m(n-1) 31 3条每行一条共3行。对于每条水平边第三个点与水平边垂直距离为2。比如水平边在第1行(1,1)-(2,1)第三个点纵坐标可以是3下方2行不存在。所以第三个点可以是(1,3)或(2,3)。但(1,3)与(1,1)和(2,1)组成的三角形是(1,1),(2,1),(1,3)面积 |1(1-3) 2*(3-1) 1*(1-1)|/2 |-240|/2 1。✓ 但(2,3)与(1,1),(2,1)组成的三角形是(1,1),(2,1),(2,3)面积 |1*(1-3) 2*(3-1) 2*(1-1)|/2 |-240|/2 1。✓ 所以对于第1行的水平边有2个第三个点选择。但我们的公式中H1 n(n-1) × 2(m-2) 212*1 4。这意味着对于每条水平边有n2个横坐标选择但纵坐标只有1种因为m-21只有上方或下方一种。所以每条水平边对应2个第三个点。3条水平边共6个。但我们的公式给出4不一致。问题出在 (\sum c(r)) 的计算。对于m3r1: c(1) [3≤3] [-1≥1] 1 0 1 r2: c(2) [4≤3] [0≥1] 0 0 0 r3: c(3) [5≤3] [1≥1] 0 1 1所以 (\sum c(r) 101 2)。H1 n(n-1) × (\sum c(r)) 212 4。但实际枚举第1行水平边(1,1)-(2,1)第三个点纵坐标可以是3横坐标可以是1或2所以2个。第3行水平边(1,3)-(2,3)第三个点纵坐标可以是1横坐标可以是1或2所以2个。第2行水平边(1,2)-(2,2)第三个点纵坐标可以是4或0都不存在所以0个。总共4个。这与公式一致。但手动枚举时我找到了3个面积为1的三角形其中(1,1),(2,1),(1,3)和(1,1),(2,1),(2,3)是两个还有(1,3),(2,3),(1,1)和(1,3),(2,3),(2,1)是两个但(1,3),(2,3),(1,1)与(1,1),(2,1),(1,3)是同一个三角形吗(1,1),(2,1),(1,3)的顶点是(1,1),(2,1),(1,3)。(1,3),(2,3),(1,1)的顶点是(1,3),(2,3),(1,1)。这两个三角形不同因为一个是底边在第1行另一个是底边在第3行。所以总共有4个水平底三角形。但手动枚举时我只找到了3个漏掉了(1,3),(2,3),(2,1)。让我验证(1,3),(2,3),(2,1)的面积|1*(3-1) 2*(1-3) 2*(3-3)|/2 |2-40|/2 1。✓ 所以确实有4个水平底三角形。那么V2呢n2, m3时V2 2m(m-2)(n-1) 2311 6。垂直底为2、高为1的三角形。垂直边有n(m-2) 21 2条列1的(1,1)-(1,3)和列2的(2,1)-(2,3)。对于列1的垂直边第三个点水平方向只能向右列2纵坐标可以是1,2,3。所以3个。对于列2的垂直边第三个点水平方向只能向左列1纵坐标可以是1,2,3。所以3个。总共6个。但其中有些三角形与水平底三角形重复。比如垂直边(1,1)-(1,3)和第三个点(2,1)这个三角形是(1,1),(1,3),(2,1)它也有水平边(1,1)-(2,1)。所以它被算在H1里作为第1行水平边的三角形和V2里。B1 4(n-1)(m-2) 411 4。所以总数为46-46。但手动枚举只有3个不同的三角形让我列出所有6个(1,1),(2,1),(1,3) - 水平底(1,1),(2,1),(2,3) - 水平底(1,3),(2,3),(1,1) - 水平底(1,3),(2,3),(2,1) - 水平底(1,1),(1,3),(2,2) - 垂直底(2,1),(2,3),(1,2) - 垂直底还有吗(1,1),(1,3),(2,1)是第1个。(1,1),(1,3),(2,3)是第3个(1,1),(1,3),(2,3)的顶点是(1,1),(1,3),(2,3)面积 |1*(3-3) 1*(3-1) 2*(1-3)|/2 |02-4|/2 1。✓ 这个三角形有垂直边(1,1)-(1,3)和水平边(1,3)-(2,3)。它被算在H1里作为第3行水平边的三角形和V2里。所以它是第3个。那么第5个(1,1),(1,3),(2,2)是新的。第6个(2,1),(2,3),(1,2)是新的。所以总共有6个不同的三角形我之前手动枚举时只找到了3个是因为我漏掉了一些。让我重新枚举n2, m3的所有6个点中任选3个的组合共有C(6,3)20种。其中面积为1的有(1,1),(2,1),(1,3) ✓(1,1),(2,1),(2,3) ✓(1,3),(2,3),(1,1) ✓ (与上面不同)(1,3),(2,3),(2,1) ✓(1,1),(1,3),(2,2) ✓(2,1),(2,3),(1,2) ✓还有吗(1,2),(2,2),(1,1)面积0.5。(1,2),(2,2),(1,3)面积0.5。(1,1),(2,2),(2,3)面积|1*(2-3)2*(3-1)2*(1-2)|/2 |-14-2|/2 0.5。(1,3),(2,2),(2,1)面积0.5。所以确实只有6个。所以公式给出6是正确的。我之前的错误在于手动枚举时漏掉了一些。这个例子说明公式在n2, m3时是正确的。但我们需要确保公式在所有边界情况下都正确。特别是当n2或m2时某些项可能为负需要特殊处理。避坑技巧在实现公式时最好先写一个暴力程序在小范围内比如n,m≤5枚举所有三角形然后与公式结果对比。如果发现不一致就打印出具体的三角形看看是公式漏算了还是多算了。这个方法能帮你快速定位问题。7. 从这道题延伸出的计数思维这道题表面上是在数三角形实际上是在训练一种非常重要的思维能力把连续的问题离散化把复杂的问题分类化。面积为1的格点三角形听起来是一个几何问题但通过“底×高2”这个条件它变成了一个整数拆分问题。再通过“水平底/垂直底”的分类它变成了几个简单的乘法计数问题。这种思维方式在算法竞赛中非常常见。很多计数题、组合题、概率题核心都是“分类讨论乘法原理”。比如数有多少个矩形按长和宽分类。数有多少个等差数列按公差分类。数有多少个回文子串按中心分类。分类的关键是不重不漏。不重就是每个对象只被算一次不漏就是每个对象都被算到。为了做到这一点你需要找到一个“唯一标识”每个对象的特征。在这道题里我们用了“水平底/垂直底”作为分类依据然后用容斥原理处理了重叠部分。另一个重要的思维是对称性。水平底和垂直底的公式是对称的这让我们可以只推导一个另一个直接交换n和m即可。对称性不仅能减少推导工作量还能帮你检查公式是否正确——如果交换n和m后公式不变或者变成对称的形式那说明公式很可能是对的。最后这道题还教会我们边界条件的重要性。n1、m1、n2、m2这些情况公式可能会失效需要单独处理。在比赛里很多人就是因为没有处理好边界条件而WA。我的习惯是先把公式在“一般情况”下推导出来然后单独测试所有小范围的情况确保公式在边界上也正确。如果你能把这道题吃透以后再遇到类似的计数问题你就有了一套可复用的方法论先暴力打表找规律再分类讨论推公式最后用容斥原理去重最后用边界测试验证。这套方法我在很多题目上都用过屡试不爽。个人体会我刚开始学算法的时候特别怕这种计数题觉得无从下手。后来我发现计数题其实比很多算法题都“老实”——它不会藏着掖着所有的信息都在题目里你只需要耐心地把情况分清楚。分情况的时候拿一张纸画几个小图把每种情况都画出来然后数一数。画着画着规律就出来了。