格点三角形计数：从O(n^6)暴力到O(n*m)高效算法

1. 从一道格点三角形题说起为什么计数类题目总让人又爱又恨算法竞赛里有一类题目看起来条件简单、图景清晰但真正动手去数的时候就会发现边界情况多到让人头皮发麻。格点三角形计数就是典型代表。题目大意是在一个 n×m 的格点矩阵中统计所有面积为特定值的三角形个数并且要求三角形的三个顶点都落在格点上。这类题在集训营里经常出现因为它同时考察了组合计数、几何直觉和取模运算三个方向的能力。我第一次遇到这类题的时候第一反应是暴力枚举三个点然后判断面积。但很快就算了一笔账如果 n 和 m 都到 10^9 级别枚举根本不可能。即便 n、m 只有几百三重循环也是 O(n^6) 的复杂度完全不可接受。所以这道题的核心矛盾在于如何把几何条件转化为可计数的代数条件再用组合数学的方式批量计算。这篇文章适合正在准备算法竞赛的选手、想提升计数类题目能力的开发者以及任何对格点几何感兴趣的人。我会从最基础的格点三角形面积公式讲起逐步推导出完整的计数方案并给出可直接复现的代码实现。过程中会重点解释每一步“为什么这样做”以及我在实际调试中踩过的坑。提示本文所有代码均使用 C 编写假设读者已经掌握基本的模运算和组合数计算。如果你对叉积求面积还不熟悉建议先补一下向量叉积的基础知识。2. 格点三角形面积的两倍公式把几何问题变成整数运算2.1 叉积与面积的关系在平面直角坐标系中假设三角形的三个顶点分别为 A(x1, y1)、B(x2, y2)、C(x3, y3)那么这个三角形的面积可以用叉积表示S |(x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)| / 2因为所有坐标都是整数所以叉积的结果一定是整数。这意味着三角形面积的两倍一定是整数。这个性质非常关键它让我们可以完全避免浮点数运算直接用整数来判断面积条件。如果题目要求面积为某个特定值比如面积为 1/2那么面积的两倍就是 1。我们只需要判断叉积的绝对值是否等于 1 即可。这样就彻底绕开了浮点精度问题。2.2 为什么格点三角形的面积一定是半整数这里有一个经典的结论格点三角形的面积一定是 0.5 的整数倍。证明很简单因为叉积是整数面积等于叉积绝对值除以 2所以面积只能是 0、0.5、1、1.5、2 等等。这个结论告诉我们如果题目要求的面积不是 0.5 的整数倍答案直接就是 0。在实际做题时我习惯先把题目要求的面积乘以 2得到一个整数目标值 target。然后问题就转化为统计所有叉积绝对值等于 target 的格点三角形个数。这一步转化是整个解题过程中最关键的思维跳跃把几何问题彻底代数化了。2.3 从叉积到向量分解直接枚举三个点仍然太慢。我们需要进一步利用格点矩阵的结构。假设我们把三角形的一个顶点固定在原点通过平移任何三角形都可以平移到一个顶点在原点的情况那么另外两个顶点可以表示为向量 u 和 v。三角形的面积两倍就是 |u × v|。在 n×m 的格点矩阵中向量的取值范围是有限的。如果我们能枚举所有可能的向量对 (u, v)使得 |u × v| target然后统计这些向量对在矩阵中能放置多少个位置就能得到答案。但向量对的数量仍然是 O(n^2 * m^2) 级别还是太大。所以我们需要更进一步的数学化简。这里要用到一个重要技巧固定一条边然后数第三个点。具体来说我们可以枚举三角形的一条边作为底边然后计算有多少个格点能使得三角形面积为 target。这样复杂度可以降到 O(n * m) 或者更低。3. 固定底边计数法从 O(n^6) 到 O(n*m) 的降维思路3.1 底边向量与高的关系假设我们固定三角形的一条边 AB其中 A 和 B 都是格点。设向量 AB (dx, dy)。对于任意一个格点 C三角形 ABC 的面积两倍等于 |dx * (yC - yA) - dy * (xC - xA)|。这个值只取决于 C 相对于 A 的位置。如果我们把 A 放在原点B 放在 (dx, dy)那么 C 的坐标 (x, y) 需要满足 |dx * y - dy * x| target。这是一个关于 x 和 y 的线性方程。对于给定的 dx 和 dy满足这个方程的格点 (x, y) 在平面上形成两条平行直线。3.2 平行直线上的格点计数方程 dx * y - dy * x target 和 dx * y - dy * x -target 分别代表两条直线。我们需要统计这两条直线上落在格点矩阵范围内的整数点个数。这里有一个数论上的结论对于方程 a * x b * y c其中 a、b、c 都是整数如果 gcd(a, b) 能整除 c那么方程有整数解且所有整数解构成一个等差数列。解的个数可以通过计算直线在矩形区域内的截距来确定。具体来说对于直线 dx * y - dy * x target我们可以把它改写成 y (dy * x target) / dx。当 dx 不为 0 时y 必须是整数所以 dy * x target 必须是 dx 的倍数。这给出了 x 需要满足的同余条件。然后我们只需要统计在矩阵范围内满足条件的 x 的个数。3.3 枚举底边的复杂度分析如果我们枚举所有可能的底边 AB那么 dx 的范围是 -n 到 ndy 的范围是 -m 到 m总共 O(n * m) 种底边向量。对于每种底边向量我们还需要枚举底边的起点位置这又是 O(n * m) 种。所以总复杂度是 O(n^2 * m^2)对于 n、m 达到 10^3 的情况就已经超时了。但我们可以进一步优化对于固定的底边向量 (dx, dy)底边的起点位置和第三个点的计数可以合并计算。实际上我们可以直接统计所有满足条件的三角形而不需要显式枚举底边起点。这需要用到一些组合计数的技巧。注意在实际比赛中n 和 m 的范围通常不会太大因为计数类题目往往需要 O(n * m) 或 O(n * m * log) 的复杂度。如果 n、m 达到 10^9那一定存在 O(1) 或 O(log) 的公式解法。读题时一定要先看数据范围这决定了你该往哪个方向思考。4. 分类讨论水平边、垂直边和斜边的不同处理方式4.1 水平底边和垂直底边的特殊情况当底边是水平的时候dy 0dx ≠ 0。此时面积两倍等于 |dx * (yC - yA)|。因为 dx 是固定的所以 |yC - yA| 必须是 target / |dx|。这意味着 target 必须能被 |dx| 整除否则这条水平底边不可能产生面积为 target 的三角形。对于水平底边第三个点 C 的 y 坐标只有两个可能的值yA target / |dx| 和 yA - target / |dx|。然后 C 的 x 坐标可以在整个矩阵范围内任意取值。所以对于每条水平底边第三个点的个数是 2 * (n 1)如果两个 y 值都在范围内的话。垂直底边的情况完全对称只是把 x 和 y 的角色互换。4.2 斜边底边的计数方法斜边的情况要复杂一些。当 dx ≠ 0 且 dy ≠ 0 时我们需要解方程 dx * y - dy * x ±target。这个方程的解可以通过扩展欧几里得算法来构造。设 g gcd(|dx|, |dy|)。如果 target 不能被 g 整除那么方程无解这条底边不产生任何三角形。如果 target 能被 g 整除那么方程有整数解且所有解可以表示为x x0 (dx / g) * t y y0 (dy / g) * t其中 (x0, y0) 是一个特解t 是任意整数。然后我们需要统计在矩阵范围内有多少个 t 使得 (x, y) 落在格点矩阵内。4.3 避免重复计数的技巧直接枚举底边会导致每个三角形被计算三次因为三角形有三条边。为了避免重复我们需要固定一个规则比如只枚举三角形的最左边的边或者只枚举满足某种条件的边。我通常采用的方法是只枚举三角形的底边并且要求第三个点严格在底边的某一侧。这样可以保证每个三角形只被计算一次。具体来说如果底边向量是 (dx, dy)我们只统计满足 dx * y - dy * x target 的点而不是 ±target这样就只计算了底边一侧的点。但这样做仍然可能重复因为同一个三角形可能有多条边满足“第三个点在某一侧”的条件。更稳妥的方法是枚举三角形的最左下角的顶点然后枚举从这个顶点出发的两条边。这样可以保证每个三角形只被计算一次。提示在实现时我建议先用小数据比如 n m 3暴力枚举所有三角形然后和你的计数算法对比确保没有重复或遗漏。这一步验证非常关键能帮你省下大量调试时间。5. 代码实现从暴力验证到高效计数的完整过程5.1 暴力枚举版本用于验证在写高效算法之前先写一个暴力版本用于验证正确性。暴力版本的思路很简单枚举三个点计算叉积判断是否等于 target。#include bits/stdc.h using namespace std; int main() { int n 3, m 3; // 格点范围0 x n, 0 y m int target 1; // 面积两倍的目标值 int cnt 0; for (int x1 0; x1 n; x1) for (int y1 0; y1 m; y1) for (int x2 0; x2 n; x2) for (int y2 0; y2 m; y2) for (int x3 0; x3 n; x3) for (int y3 0; y3 m; y3) { int cross abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)); if (cross target) cnt; } cout cnt / 6 endl; // 每个三角形被枚举了 6 次 return 0; }这个暴力版本虽然慢但逻辑绝对正确。我建议先用它跑出小数据的结果作为后续算法的对照标准。5.2 固定底边的高效版本高效版本的核心思路是枚举底边向量 (dx, dy)然后对于每个底边向量计算在矩阵中有多少条这样的底边以及每条底边对应多少个第三个点。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1e9 7; ll n, m, target; // 计算 gcd ll gcd(ll a, ll b) { return b 0 ? a : gcd(b, a % b); } // 扩展欧几里得求解 ax by g ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; return a; } ll g exgcd(b, a % b, y, x); y - (a / b) * x; return g; } int main() { cin n m target; ll ans 0; // 枚举底边向量 (dx, dy)其中 dx 0 for (ll dx -n; dx n; dx) { for (ll dy -m; dy m; dy) { if (dx 0 dy 0) continue; // 只枚举一个方向的底边避免重复 if (dx 0 || (dx 0 dy 0)) continue; ll g gcd(abs(dx), abs(dy)); if (target % g ! 0) continue; // 计算底边在矩阵中的放置方式数 ll edgeCnt (n - abs(dx) 1) * (m - abs(dy) 1); // 计算每条底边对应的第三个点个数 // 这里需要解方程 dx * y - dy * x target // 具体实现略需要根据 dx, dy 的正负分类讨论 // ... } } cout ans % MOD endl; return 0; }5.3 边界情况的处理在实际实现中有几个边界情况需要特别注意第一当 dx 0 或 dy 0 时方程退化为简单的一元方程需要单独处理。第二当 target 0 时意味着三角形面积为 0即三个点共线这种情况通常题目不会要求但代码中需要排除。第三当 n 或 m 为 0 时格点矩阵退化为一条线不可能形成三角形答案直接为 0。我在调试时发现最容易出错的地方是第三个点的范围判断。因为第三个点必须在格点矩阵内所以它的 x 坐标必须在 0 到 n 之间y 坐标必须在 0 到 m 之间。在解方程得到通解后需要根据这两个不等式确定 t 的取值范围然后计算整数 t 的个数。注意在计算 t 的个数时要注意整数除法的方向。如果不等式的边界不是整数需要向上或向下取整。我建议直接用循环枚举 t 的范围虽然慢一点但不容易出错。等验证正确后再优化成公式计算。6. 取模运算与组合数计数类题目的最后一道坎6.1 为什么计数类题目总要取模算法竞赛中计数类题目的答案往往非常大比如 n 10^5 时三角形个数可能达到 10^15 级别远超 64 位整数的范围。所以题目通常会要求答案对 10^97 取模。取模本身不难难的是在计数过程中如何正确地取模避免中间结果溢出。我的经验是所有涉及乘法的中间结果都要用 long long 存储并且在每次乘法后立即取模。加法可以最后统一取模但乘法必须步步取模。另外如果涉及到减法要记得加上 MOD 再取模避免出现负数。6.2 组合数计算的预处理如果题目需要用到组合数比如从 n 个点中选 3 个点那么需要预处理阶乘和逆元。标准做法是const int MAXN 1e6 5; ll fact[MAXN], inv_fact[MAXN]; ll power(ll a, ll b, ll mod) { ll res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } void init() { fact[0] 1; for (int i 1; i MAXN; i) fact[i] fact[i-1] * i % MOD; inv_fact[MAXN-1] power(fact[MAXN-1], MOD-2, MOD); for (int i MAXN-2; i 0; i--) inv_fact[i] inv_fact[i1] * (i1) % MOD; } ll C(int n, int k) { if (k 0 || k n) return 0; return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD; }这套模板我几乎每场比赛都会用到建议直接背下来。需要注意的是MAXN 的大小要根据题目数据范围来定开太小会越界开太大会浪费内存。6.3 避免重复计数的取模技巧在计数过程中我们经常需要除以某个数来去重。比如每个三角形被计算了 6 次最后答案要除以 6。但在模运算下除法要转化为乘以逆元。所以答案是 ans * power(6, MOD-2, MOD) % MOD。这里有一个常见的坑如果 ans 在取模之前就已经被模掉了那么除以 6 的结果可能不正确。正确的做法是在计数过程中不取模或者用一个额外的变量记录真实值最后再统一取模。如果数据范围太大必须取模那么要确保计数过程中没有除法或者除法都在模运算下正确进行。我在一次比赛中就踩过这个坑中间结果取了模最后除以 6 的时候用了逆元但因为没有确保 ans 是 6 的倍数在模意义下导致答案错误。后来改成所有计数都不取模用 Python 的大整数计算最后再取模才通过了。所以如果数据范围允许我建议先用不取模的方式验证正确性再改成取模版本。7. 从这道题延伸出的计数类题目通用套路7.1 枚举维度选择固定什么枚举什么计数类题目的核心艺术在于选择枚举的维度。一般来说我们要枚举那些“组合数较少”的维度然后对于每个枚举值用公式批量计算其他维度的贡献。在这道题中我们选择枚举底边向量 (dx, dy)因为底边向量的种类是 O(n * m) 级别而第三个点的位置可以用公式直接算出来。如果反过来枚举第三个点然后数底边复杂度会更高。这个思路可以推广到很多计数类题目先找到问题中“自由度”最小的部分枚举它然后其他部分用组合数学批量处理。7.2 容斥原理在计数中的应用有些计数类题目直接数不好数但可以用容斥原理先数所有情况再减去不满足条件的情况。比如统计格点三角形个数时可以先数所有三点组合再减去三点共线的情况。容斥原理的关键是不重不漏。我通常会把所有需要减去的情况列一个表然后逐一确认每种情况被减了几次确保最终结果正确。7.3 对称性利用减少一半枚举量格点矩阵通常具有对称性。比如 n×m 的矩阵关于中心对称那么很多计数可以只算一半然后乘以 2。但要注意对称轴上的情况需要单独处理不能简单乘以 2。在这道题中我们可以只枚举 dx 0 的底边向量然后对于 dx 0 的情况乘以 2对于 dx 0 的情况单独处理。这样可以减少一半的枚举量。提示利用对称性时一定要仔细检查对称轴上的元素是否被重复计算。我见过很多选手因为对称性处理不当导致答案偏大或偏小。8. 调试与验证如何确保你的计数结果是对的8.1 小数据暴力对拍这是最可靠的验证方法。写一个暴力程序再写一个高效程序随机生成小数据比如 n、m 在 1 到 5 之间对比两个程序的输出。如果所有测试都一致那么高效程序的正确性就有很大保障。我通常会写一个脚本自动生成 1000 组小数据然后逐一对比。这个过程虽然枯燥但能发现绝大多数逻辑错误。8.2 边界数据测试除了随机数据还要专门测试边界情况n 0、m 0、target 0、target 非常大、target 是奇数等等。这些情况往往能暴露代码中的隐藏 bug。比如当 target 是奇数时如果面积两倍是奇数那么三角形面积是半整数这是合法的。但如果 target 是负数那就不合法应该输出 0。这些细节都需要在代码中处理。8.3 性能测试最后用大数据测试程序的运行时间。如果 n、m 达到 10^3O(n * m) 的算法应该能在 1 秒内跑完。如果超时就需要进一步优化比如用前缀和或者数学公式。我在实际比赛中通常会先写一个 O(n * m) 的版本如果超时再想办法优化。因为 O(n * m) 的版本逻辑简单不容易出错而且往往能拿到大部分分数。9. 我在实战中总结的几条经验第一先想清楚再写代码。计数类题目最容易出现的问题就是重复计数或遗漏计数。在动手之前一定要把计数方案想清楚最好在纸上画一画确认每个三角形只被计算一次。第二暴力验证不可少。不管你的算法看起来多正确都要用暴力程序验证。我见过太多“看起来没问题”的代码一跑就错。第三注意数据范围。n、m 的范围决定了你该用什么复杂度的算法。如果 n、m 达到 10^9那一定存在 O(1) 的公式不要浪费时间写 O(n * m) 的代码。第四取模要小心。所有乘法都要用 long long所有减法都要加 MOD除法要转逆元。这些细节看似简单但比赛中因为取模出错而丢分的情况非常常见。第五多总结套路。计数类题目虽然变化多端但核心套路就那么几个枚举维度选择、容斥原理、对称性利用、组合数计算。把这几个套路练熟遇到新题就能快速找到思路。最后分享一个我常用的小技巧在写计数类题目时我会先用 Python 写一个暴力版本因为 Python 的大整数运算不用担心溢出写起来也快。然后用 C 写高效版本用 Python 的暴力版本对拍。这样既能快速验证思路又能保证最终代码的性能。