LeetCode 补充题 187. 金字塔前 n 层的格点数
题目描述
牛客原题： ✅ 补充题 187. 金字塔前 n 层的格点数
第
i层有i(i+1)/2个点，求前n层总点数，结果模1000000007。
示例 1：
输入：
n = 4
输出：20
解释： 前四层分别有 1、3、6、10 个点，总和为 20。
提示：
-
n表示层数；第i层点数为i(i+1)/2。 - 答案对
1000000007取模。
题意分析
第
i层点数是三角形数i(i+1)/2，前n层可以整体求和，不需要逐层生成点。将三角形数写成组合数后，累加可化为一个三次乘积公式。计算公式时还要区分普通整数除法与模运算中的除法；提前取模后需乘以 6 的模逆元，不能将余数直接整除 6。
解法：组合恒等式与模逆元
核心思路
[!blue]
先解释点数从哪里来：第
i层有1+2+…+i = C(i+1,2)个点。把各层相加，利用组合数的逐层累加恒等式，得到C(n+2,3) = n(n+1)(n+2)/6；因此无需真的逐层循环。计算答案时对
P = 1000000007取模。取模后不能再直接做普通整数除以 6，而要乘 6 的模逆元166666668，它满足乘以 6 后模 P 等于 1。代码先把 n 归入模 P 的范围，再逐次乘三个相邻因子并取模，最后乘逆元。例如前两层分别有 1、3 个点，总数为 4，与
2*3*4/6一致。面试先讲清分层计数与公式，再解释模除法，避免把逆元常量当成无来源的数字。
解题步骤
- 累加第 i 层的三角形数，化简为 n(n+1)(n+2)/6。
- 先对 n 取模，再计算三个相邻因子，每次乘法后立即取模。
- 乘 6 的模逆元 166666668 后再次取模。
代码实现
class Solution {
public long points(long n) {
long p = 1_000_000_007;
n %= p;
return n * ((n + 1) % p) % p * ((n + 2) % p) % p * 166666668 % p;
}
}
func points(n int64) int64 {
const p int64 = 1_000_000_007
n %= p
return n * ((n + 1) % p) % p * ((n + 2) % p) % p * 166666668 % p
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
逆元成立是因为模数为素数且不整除 6；提前取模还要覆盖加法，不能等 n+2 已溢出后才取模。
易错点总结
[!yellow]
- 先把 n 对 P 取模，再做 +1、+2，避免 n 接近 64 位上限时加法溢出。
- 每次只乘两个小于 P 的因子并取模，乘积仍在 64 位有符号整数范围内。
- 模意义下除以 6 要乘逆元，不能直接做整数除法。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 62. 不同路径 | 中等 | 网格路径也可用组合数计数，n≥1 时 4×n 网格的路径数同样是 C(n+2,3)。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！