数三角形(二)(Count Triangles II)
数三角形(二)(Count Triangles II)
题目描述
给定一个由 n×m 个方格组成的网格图，若从这个网格图中任意挑选三个格点（格点就是网格图中某个方格的某个顶点），请问有多少种组合可以让这三个点成为三角形的顶点？
输入格式
两个整数：n 和 m。
输出格式
单个整数：表示三角形的数量。
样例输入 #1
1 1
样例输出 #1
4
样例输入 #2
2 2
样例输出 #2
76
数据范围
- 对 30% 的数据，1 ≤ n, m ≤ 10
- 对 60% 的数据，1 ≤ n, m ≤ 500
- 对 100% 的数据，1 ≤ n, m ≤ 3000
知识点与难度
本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。
测试点分布
| Subtask | 分值 | 测试点编号 | 说明 |
|---|---|---|---|
| 0 | 10 | 1~2 | 样例 |
| 1 | 20 | 3~8 | 小规模 n,m≤10 / 特殊: n=1 / m=1 |
| 2 | 15 | 9~11 | Hack: n=m / 极端矩形 |
| 3 | 30 | 12~20 | 中规模 n,m≈100~500 |
| 4 | 25 | 21~25 | 大规模 n,m≈3000 压力 |