数学题是信息学竞赛中重要的一类题目，通常包括几何、数论、容斥原理等。
本文将相关的题目归纳整理，用于教学。
几何
P2241 统计方形
本题解法：每个矩形（包括正方形）都可以由一段左边线段和一段上边线段确定。因此，我们只需要枚举所有可能的线段。
对于一个长是 N 宽是 M 的棋盘。
- 左边的线段长度为 1 的有 N 个，长度为 2 的有 N-1 个，…长度为 N 的有 1 个。
- 上边的线段长度为 1 的有 M 个，长度为 2 的有 M-1 个，…长度为 M 的有 1 个。
所以:
- 左边的线段一共有
（1+2+3+...+N）= N*(N+1)/2个。 - 上边的线段一共有
（1+2+3+...+M）= M*(M+1)/2个。 - 因此，总共有
N*(N+1)/2 * M*(M+1)/2个矩形。
用相同的办法可以推导正方形的数量，方法如下：
- 对于左边长度为 1 的线段有 N 个，相应的上边长度为 1 的线段有 M 个。
- 所以可以构造出
N*M个边长为 1 的正方形。
同理：
- 对于左边长度为 2 的线段有 N-1 个，相应的上边长度为 2 的线段有 M-1 个。
- 所以可以构造出
(N-1)*(M-1)个边长为 2 的正方形。
以此类推，可以构造出 N*M + (N-1)*(M-1) + (N-2)*(M-2) + (N-M+1)*1 个正方形(N>M)。
另外，需要注意使用 long long 来保存结果。完整的代码如下：
1 |
|