数学题是信息学竞赛中重要的一类题目，通常包括几何、数论、容斥原理等。

本文将相关的题目归纳整理，用于教学。

几何

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
2
3
4
5
6
7
8
9
10
11
12
13

#include <bits/stdc++.h>
using namespace std;
unsigned long long n, m, ans1, ans2;
int main() {
    cin >> n >> m;
    ans1 = n*(n+1)/2 * m*(m+1)/2;
    while (n > 0 && m > 0) {
        ans2 += n*m;
        n--; m--;
    }
    cout  << ans2 << " " << ans1 - ans2 << endl;
    return 0;
}

数论

P1044 栈

这道题可以先用暴力的办法把前面几个数打出来，然后我们能发现数的规律是：1,1,2,5,14,42,132,429,1430,….

这是计算组合中很常见的卡特兰数，卡特兰数有两种公式，第一种公式是：

• f(n) = f(n-1) * (4 * n - 2) / (n + 1)

我个人觉得这个公式不太好记。另一个公式是：

这个递推式相对好记一点：即C(n) = C(0)*C(n-1) + C(1)*C(n-2) ... C(n-1)*C(0)

以下是用该递推式实现的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

long long ans[19];
int main() {
    int n;
    cin >> n;
    ans[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; ++j) {
            ans[i] += ans[j] * ans[i-1-j];
        }
    }
    cout << ans[n] << endl;
    return 0;
}