LeetCode 补充题 164. 格点阵中的轴平行直角三角形计数
题目描述
牛客原题： ✅ 补充题 164. 格点阵中的轴平行直角三角形计数
在
n行m列格点中，选三个点组成直角三角形，且两条直角边分别平行于横轴、纵轴。返回三角形个数对
1000000007取模的结果。n、m表示点数，不是小方格数量。
示例 1：
输入：
n = 2, m = 3
输出：12
解释： 直角顶点有 6 种选择，同一行另一个点有 2 种、同一列另一个点有 1 种，共6×2×1=12种。
提示：
-
n、m为正整数，分别表示格点的行数、列数。 - 三个顶点互不相同，两条直角边必须轴平行。
- 答案对
1000000007取模。
题意分析
两条直角边分别水平和竖直，使直角顶点的位置唯一确定。先固定它，再独立选择同行和同列的另两个顶点，就能直接应用乘法计数，避免枚举三个点再判定。
解法：固定直角顶点后相乘计数
核心思路
[!blue]
直角顶点有
n*m种选法，同行另一个点有m-1种，同列另一个点有n-1种。后二者都排除直角顶点，且各自方向不同，所以三个点必然互不相同，构成非退化直角三角形。每个合格三角形只有一个直角顶点，横边端点和竖边端点角色也唯一，因此总数为
n*m*(n-1)*(m-1)，不需要再除以 2 或 6。每个因子先取模，每次乘法后立即取模。模数约为十亿，两个余数乘积可放入 64 位，但四个因子直接相乘可能溢出。一行或一列时某个因子为 0，答案自然为 0。
解题步骤
- 选择直角顶点，共 n×m 种。
- 在它同行选另一个点，再在同列选第三点，分别有 m-1、n-1 种。
- 逐次乘法后取模，返回 n×m×(n-1)×(m-1) 的模值。
代码实现
class Solution {
public long triangles(long n, long m) {
long p = 1_000_000_007;
return n % p * (m % p) % p * ((n - 1) % p) % p * ((m - 1) % p) % p;
}
}
func triangles(n, m int64) int64 {
const p int64 = 1_000_000_007
return n % p * (m % p) % p * ((n - 1) % p) % p * ((m - 1) % p) % p
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
每个符合条件的三角形只有一个直角顶点，横边与竖边角色固定，因此没有额外的重复因子要除掉。
易错点总结
[!yellow]
斜着的直角边不符合题意；一行或一列时答案为0；不存在额外除2或除6。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 3128. 直角三角形 | 中等 | 稀疏二值网格中按每个顶点的同行、同列点数计数；完整格点阵中这两个数量固定为 m-1、n-1。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！