解题思路

莱布尼茨三角形也叫“调和三角形”，它长这样：

第 1 行：  1/1
第 2 行：  1/2  1/2
第 3 行：  1/3  1/6  1/3
第 4 行：  1/4  1/12 1/12 1/4
第 5 行：  1/5  1/20 1/30 1/20 1/5

观察图片和上面的例子，可以发现一个规律：第 n 行第 m 个数（从左边数第 m 个）等于 1 / ( n × C(n-1, m-1) )。其中 C(n-1, m-1) 是组合数，也就是杨辉三角第 n-1 行第 m-1 列的那个数。

验证一下样例 n=7、m=3：

• 组合数 C(6, 2) = (6×5)/(2×1) = 15；
• 分母 = 7 × 15 = 105；
• 所以答案是 1/105。和样例完全一致！

所以题目就变成了：求组合数 C(n-1, m-1)，再乘上 n，输出 “1/分母”。

组合数怎么算？按定义：

C(a, b) = a × (a-1) × ... × (a-b+1) 除以 1 × 2 × ... × b。

写程序时用“边乘边除”的办法，每一步都能保证得到整数结果：

参考代码

c = 1;
for (i = 0; i < k; i++) c = c * (a - i) / (i + 1);

还可以利用对称性 C(a, b) = C(a, a-b)：如果 b 比 a-b 大，就把 b 换成 a-b，循环次数更少。

注意：n 最大是 30，C(29, 14) 已经接近 8 千万，再乘上 n 会超过 int 的范围，所以要用 long long。

// P4436 莱布尼茨三角形：第 n 行第 m 个数 = 1 / ( n * C(n-1, m-1) )
#include <iostream>
using namespace std;

int main() {
    int n, m; // n 行第 m 个位置
    cin >> n >> m;

    int k = m - 1;        // 组合数 C 的下标：从 n-1 个里选 m-1 个
    int nn = n - 1;       // 组合数的上标
    if (k > nn - k) k = nn - k; // 用对称性 C(a,b)=C(a,a-b)，少算一些

    long long c = 1;      // 计算组合数 C(n-1, m-1)
    for (int i = 0; i < k; i++) {
        c = c * (nn - i) / (i + 1); // 乘除交替，保证每一步都是整数
    }

    long long den = 1LL * n * c; // 分母 = n * C(n-1, m-1)
    cout << 1 << "/" << den << endl; // 输出分数，格式是 1/分母
    return 0;
}

复杂度分析

• 组合数最多算约 n/2 次乘法除法，n 最大 30，时间复杂度是 O(n)。
• 只用了一小把变量，空间复杂度是 O(1)。