解题思路

杨辉三角有一个非常重要的性质：第 n 行第 m 列的数，等于组合数 C(n-1, m-1)。

为什么？因为杨辉三角的每一行其实就是二项式展开的系数，而组合数正好就是这些系数。比如第 5 行是：

1  4  6  4  1

这一行就是 C(4,0)、C(4,1)、C(4,2)、C(4,3)、C(4,4)。所以第 5 行第 3 列 = C(4,2) = 6，和样例一致。

于是题目就变成了：求组合数 C(n-1, m-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) 减少循环次数。注意 n 最大 30，虽然结果不算特别大，但中间计算用 long long 更保险。

// P4439 杨辉三角数字：第 n 行第 m 列的值就是组合数 C(n-1, m-1)
#include <iostream>
using namespace std;

int main() {
    int n, m; // 行和列
    cin >> n >> m;

    // 杨辉三角第 n 行第 m 个 = C(n-1, m-1)
    int k = m - 1;           // 组合数下标
    int nn = n - 1;          // 组合数上标
    if (k > nn - k) k = nn - k; // 利用对称性减少计算

    long long c = 1;         // 计算组合数
    for (int i = 0; i < k; i++) {
        c = c * (nn - i) / (i + 1); // 每步结果都是整数
    }

    cout << c << endl; // 输出第 n 行第 m 列的数值
    return 0;
}

复杂度分析

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