企业官网建设流程全解析

1. 从一道计数题说起：格点三角形到底在数什么

第一次看到“honoka和格点三角形”这个题目名，很多人会愣一下——honoka是谁？其实这不重要，重要的是后面那五个字：格点三角形。所谓格点，就是平面直角坐标系里横纵坐标都是整数的点，比如(0,0)、(1,2)、(-3,5)这些。格点三角形，就是三个顶点全都落在格点上的三角形。

这道题的核心要求通常是这样的：在一个 (n \times m) 的格点矩阵里（也就是横坐标从1到n、纵坐标从1到m的所有整点），统计面积为1的格点三角形有多少个。注意，是面积为1，不是面积为1/2。这个区别非常关键，因为格点三角形的面积有个著名结论——要么是整数，要么是半整数。面积为1的三角形，意味着它的“底乘高”等于2，这就把问题转化成了对底和高的整数拆分。

为什么这道题值得单独拿出来讲？因为它是一道典型的计数类问题，考的不是什么高深算法，而是你能不能把一个大问题拆成几个互不重叠的小情况，然后用乘法原理和加法原理干净利落地算出来。很多人在比赛里栽跟头，不是因为不会写代码，而是因为分类的时候漏了情况、或者算重了。我见过太多人在这道题上WA（Wrong 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，即y=2或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行，可选的第三个点纵坐标有：(r+2)（如果 (r \leq m-2)）和 (r-2)（如果 (r \geq 3)）。数量为：

• 如果 (3 \leq r \leq m-2)：2个选择。
• 如果 (r = 1) 或 (r = 2)：只有下方？不对，r=1时下方2行是-1，不存在；上方2行是3，如果m≥3则存在。所以r=1时只有上方1个选择（如果m≥3）。r=2时上方4存在（如果m≥4），下方0不存在。等等，我需要重新理清。

让我用更简单的方法：对于每一行r，第三个点的纵坐标可以是r+2或r-2，只要它们在1到m之间。所以对于第r行，可选的纵坐标数量是：

[ c(r) = [r+2 \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_{r=1}^{m} c(r) ]

其中 (\sum_{r=1}^{m} c(r)) 是所有行中可选的纵坐标总数。

计算 (\sum_{r=1}^{m} c(r))：

• 对于r=1：c(1) = [3≤m] + [−1≥1] = [m≥3] + 0 = [m≥3]。
• 对于r=2：c(2) = [4≤m] + [0≥1] = [m≥4]。
• 对于r=3到m-2：c(r) = 2（如果m≥5）。
• 对于r=m-1：c(m-1) = [m+1≤m] + [m-3≥1] = 0 + [m≥4] = [m≥4]。
• 对于r=m：c(m) = [m+2≤m] + [m-2≥1] = 0 + [m≥3] = [m≥3]。

这个求和有点繁琐，但可以化简。实际上，我们可以换个角度：所有可能的(水平边, 第三个点)组合，等价于选择一条水平边和一条与之平行且距离为2的直线上的一个点。

更简单的方法：考虑所有可能的“底边+高”的组合。水平边有 (m(n-1)) 条。对于每条水平边，第三个点的纵坐标有c(r)种选择，横坐标有n种选择。所以 (H_1 = n \times \sum_{r=1}^{m} (n-1) \times c(r) = n(n-1) \sum_{r=1}^{m} c(r))。

而 (\sum_{r=1}^{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到m，r'可以是r+2或r-2。所以总数是 (2(m-2))（因为r+2≤m的有m-2个，r-2≥1的有m-2个，总共2(m-2)）。

因此：

[ H_1 = n(n-1) \times 2(m-2) ]

这个公式在m≥3时成立。如果m<3，则 (H_1 = 0)。

子类型H2：底为2、高为1

水平边的两个端点横坐标相差2。在每一行，有n-2条这样的水平边（如果n≥3）。水平边的总数是 (m(n-2))。

第三个点与水平边的垂直距离为1，即纵坐标为r+1或r-1。

类似地，对于每一行r，可选的纵坐标数量是：

[ d(r) = [r+1 \leq m] + [r-1 \geq 1] ]

对于r=1：d(1) = [2≤m] + 0 = [m≥2]。 对于r=m：d(m) = 0 + [m-1≥1] = [m≥2]。 对于2≤r≤m-1：d(r) = 2。

所以 (\sum_{r=1}^{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_{r=1}^{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，即横坐标为c+2或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)，水平边的另一个端点在(c+1, r)或(c-1, r)，垂直边的另一个端点在(c, r+2)或(c, r-2)。

所以对于每个直角顶点，有2种水平方向（左或右）× 2种垂直方向（上或下）= 4种选择。但需要满足边界条件。

实际上，我们可以这样算：水平边为1意味着直角顶点和水平边的另一个端点相邻。垂直边为2意味着直角顶点和垂直边的另一个端点纵坐标相差2。

对于每个可能的直角顶点(c, r)：

• 水平方向：c+1≤n 或 c-1≥1，所以有 ([c<n] + [c>1]) 种选择。
• 垂直方向：r+2≤m 或 r-2≥1，所以有 ([r≤m-2] + [r≥3]) 种选择。

所以B1的总数是：

[ B_1 = \sum_{c=1}^{n} \sum_{r=1}^{m} ([c<n] + [c>1]) \times ([r≤m-2] + [r≥3]) ]

这个求和可以化简。(\sum_{c=1}^{n} ([c<n] + [c>1]) = (n-1) + (n-1) = 2(n-1))。

(\sum_{r=1}^{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) ]

这个公式看起来有点长，但每一项都有明确的几何意义。我们可以进一步化简，但保留这个形式更便于理解。

实操心得：在比赛里，我建议先把公式写成这种“分项”的形式，然后逐项验证。比如，当n=3, m=3时，手动枚举所有面积为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)这样的因子）。比如n=2时，n-2=0，H2=0，这没问题；但V1中有(n-2)因子，也会变成0。但如果n=1，n-2=-1，就会出现负数。所以我们需要在n<3时把相关项置零。

第二，公式中的乘法可能会溢出。即使n和m在10^9以内，n*(n-1)*(m-2)这样的乘积可能达到10^27级别，远超long long的范围（约9×10^18）。所以如果题目中n和m很大，需要在乘法过程中取模，或者使用大数运算。但通常这类题目会要求结果对某个数取模，比如10^9+7。如果题目没有要求取模，那n和m的范围应该不会太大。

第三，边界情况：n=1或m=1时，格点退化成一条线，无法构成三角形，返回0。n=2且m=2时，只有4个格点，任选3个组成三角形，面积最大为0.5（比如(1,1),(2,1),(1,2)面积为0.5），所以面积为1的三角形数量为0。我们的公式在n=2,m=2时：H1=2210=0，H2=2201=0，V1=2210=0，V2=2201=0，B1=410=0，B2=401=0，总数为0，正确。

注意：在实际比赛中，如果n和m的范围达到10^9，而结果没有要求取模，那说明结果本身不会太大？这不太可能。更常见的是要求对10^9+7取模。这时候需要在每一步乘法后取模，并且减法时要加上模数再取模，避免负数。

6. 常见错误与排查技巧

这道题虽然思路清晰，但在实际编码中很容易出错。我整理了几个常见的坑：

错误一：重复计数

最常见的错误就是没有处理好直角三角形。如果直接计算H+V而不减去B，结果会偏大。我见过有人把H和V直接相加，然后发现答案比预期大很多，就是因为直角三角形被算了两次。

错误二：边界条件处理不当

当n或m较小时，某些项会变成负数。比如n=2时，H2中的(n-2)因子为0，这没问题；但V1中的(n-2)因子也为0，V2中的(n-1)因子为1，但V2还有(m-2)因子，如果m≥3，V2可能不为0。但实际上n=2时，格点只有两列，垂直底三角形的第三个点需要水平距离为1或2，但只有两列，水平距离最大为1，所以V2应该为0。我们的公式中V2 = 2m(m-2)(n-1)，当n=2时，n-1=1，V2 = 2m(m-2)，这不为0！这说明我们的公式在n=2时有问题。

让我重新检查V2的推导。V2是垂直底为2、高为1的情况。垂直边的两个端点纵坐标相差2，第三个点与垂直边的水平距离为1。当n=2时，只有两列，水平距离为1意味着第三个点必须在相邻的列。但垂直边本身占了一列，第三个点在另一列，这是可能的。比如垂直边在列1，从(1,1)到(1,3)，第三个点在列2，纵坐标可以是2（与垂直边的中点同高），这样三角形(1,1),(1,3),(2,2)的面积为1。所以n=2时确实存在这样的三角形。

那么V2的公式在n=2时应该是多少？垂直边在列1，有m-2条（纵坐标从1到m-2）。第三个点在列2，纵坐标可以是垂直边两个端点之间的任意整数？不对，高为1意味着第三个点到垂直边的水平距离为1，但垂直距离（即第三个点的纵坐标与垂直边的“底”的垂直距离）需要仔细定义。

实际上，对于垂直底为2、高为1的情况，垂直边的两个端点纵坐标相差2，第三个点的横坐标与垂直边相差1。第三个点的纵坐标可以是任意值吗？不是，因为面积 = 底 × 高 / 2 = 2 × 1 / 2 = 1。这里的高是第三个点到垂直边所在直线的水平距离，即1。但垂直边所在直线是x=c，第三个点在x=c±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)。但这样算的话，当n=2时，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条。第三个点的水平方向：如果c=1，只能向右（1种）；如果c=n，只能向左（1种）；如果1<c<n，可以向左或向右（2种）。

所以对于第c列，第三个点的水平选择数 = [c>1] + [c<n]。

总水平选择数 = (\sum_{c=1}^{n} ([c>1] + [c<n]) = (n-1) + (n-1) = 2(n-1))。

所以V2 = (m-2) × 2(n-1) × m = 2m(m-2)(n-1)。

这个公式在n=2时给出V2 = 2m(m-2)(1) = 2m(m-2)。但n=2时，总水平选择数 = (2-1)+(2-1) = 2，所以V2 = (m-2) × 2 × m = 2m(m-2)。这与公式一致。

但之前我说n=2时V2应该为0，那是错误的。n=2时确实存在垂直底为2、高为1的三角形。比如(1,1),(1,3),(2,2)，面积为1。所以V2不为0。

那么为什么我之前认为n=2时V2应该为0？因为我误以为水平距离为1意味着第三个点必须在相邻列，而n=2时只有两列，垂直边占一列，第三个点在另一列，这是可能的。所以V2在n=2时不为0。

那么n=2时，总数量是多少？让我们手动枚举n=2, m=3的情况。格点有(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 = |1+1-4|/2 = 2/2 = 1。✓
• (1,1),(2,1),(2,3)：面积 = |1*(1-3) + 2*(3-1) + 2*(1-1)|/2 = |-2+4+0|/2 = 1。✓
• (1,3),(2,3),(2,1)：面积 = |1*(3-1) + 2*(1-3) + 2*(3-3)|/2 = |2-4+0|/2 = 1。✓
• (1,2),(2,2),(1,1)：面积 = |1*(2-1) + 2*(1-2) + 1*(2-2)|/2 = |1-2+0|/2 = 0.5。✗
• (1,1),(1,2),(2,3)：面积 = |1*(2-3) + 1*(3-1) + 2*(1-2)|/2 = |-1+2-2|/2 = 0.5。✗

所以n=2, m=3时，面积为1的三角形有3个。

用我们的公式：n=2, m=3。

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) = 0

Total = 4 + 0 + 0 + 6 - 4 - 0 = 6。

但手动枚举只有3个！这说明公式有问题。

让我重新检查H1的计算。n=2, m=3时，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 = |-2+4+0|/2 = 1。✓ 但(2,3)与(1,1),(2,1)组成的三角形是(1,1),(2,1),(2,3)，面积 = |1*(1-3) + 2*(3-1) + 2*(1-1)|/2 = |-2+4+0|/2 = 1。✓ 所以对于第1行的水平边，有2个第三个点选择。但我们的公式中，H1 = n(n-1) × 2(m-2) = 212*1 = 4。这意味着对于每条水平边，有n=2个横坐标选择，但纵坐标只有1种（因为m-2=1，只有上方或下方一种）。所以每条水平边对应2个第三个点。3条水平边共6个。但我们的公式给出4，不一致。

问题出在 (\sum c(r)) 的计算。对于m=3：

r=1: c(1) = [3≤3] + [-1≥1] = 1 + 0 = 1 r=2: c(2) = [4≤3] + [0≥1] = 0 + 0 = 0 r=3: c(3) = [5≤3] + [1≥1] = 0 + 1 = 1

所以 (\sum c(r) = 1+0+1 = 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-4+0|/2 = 1。✓ 所以确实有4个水平底三角形。

那么V2呢？n=2, m=3时，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。所以总数为4+6-4=6。

但手动枚举只有3个不同的三角形？让我列出所有6个：

1. (1,1),(2,1),(1,3) - 水平底
2. (1,1),(2,1),(2,3) - 水平底
3. (1,3),(2,3),(1,1) - 水平底
4. (1,3),(2,3),(2,1) - 水平底
5. (1,1),(1,3),(2,2) - 垂直底
6. (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 = |0+2-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个，是因为我漏掉了一些。让我重新枚举n=2, m=3的所有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 = |-1+4-2|/2 = 0.5。(1,3),(2,2),(2,1)面积0.5。所以确实只有6个。

所以公式给出6是正确的。我之前的错误在于手动枚举时漏掉了一些。

这个例子说明，公式在n=2, m=3时是正确的。但我们需要确保公式在所有边界情况下都正确。特别是当n=2或m=2时，某些项可能为负，需要特殊处理。

避坑技巧：在实现公式时，最好先写一个暴力程序，在小范围内（比如n,m≤5）枚举所有三角形，然后与公式结果对比。如果发现不一致，就打印出具体的三角形，看看是公式漏算了还是多算了。这个方法能帮你快速定位问题。

7. 从这道题延伸出的计数思维

这道题表面上是在数三角形，实际上是在训练一种非常重要的思维能力：把连续的问题离散化，把复杂的问题分类化。面积为1的格点三角形，听起来是一个几何问题，但通过“底×高=2”这个条件，它变成了一个整数拆分问题。再通过“水平底/垂直底”的分类，它变成了几个简单的乘法计数问题。

这种思维方式在算法竞赛中非常常见。很多计数题、组合题、概率题，核心都是“分类讨论+乘法原理”。比如：

• 数有多少个矩形：按长和宽分类。
• 数有多少个等差数列：按公差分类。
• 数有多少个回文子串：按中心分类。

分类的关键是不重不漏。不重，就是每个对象只被算一次；不漏，就是每个对象都被算到。为了做到这一点，你需要找到一个“唯一标识”每个对象的特征。在这道题里，我们用了“水平底/垂直底”作为分类依据，然后用容斥原理处理了重叠部分。

另一个重要的思维是对称性。水平底和垂直底的公式是对称的，这让我们可以只推导一个，另一个直接交换n和m即可。对称性不仅能减少推导工作量，还能帮你检查公式是否正确——如果交换n和m后公式不变（或者变成对称的形式），那说明公式很可能是对的。

最后，这道题还教会我们边界条件的重要性。n=1、m=1、n=2、m=2这些情况，公式可能会失效，需要单独处理。在比赛里，很多人就是因为没有处理好边界条件而WA。我的习惯是：先把公式在“一般情况”下推导出来，然后单独测试所有小范围的情况，确保公式在边界上也正确。

如果你能把这道题吃透，以后再遇到类似的计数问题，你就有了一套可复用的方法论：先暴力打表找规律，再分类讨论推公式，最后用容斥原理去重，最后用边界测试验证。这套方法我在很多题目上都用过，屡试不爽。

个人体会：我刚开始学算法的时候，特别怕这种计数题，觉得无从下手。后来我发现，计数题其实比很多算法题都“老实”——它不会藏着掖着，所有的信息都在题目里，你只需要耐心地把情况分清楚。分情况的时候，拿一张纸，画几个小图，把每种情况都画出来，然后数一数。画着画着，规律就出来了。