帕斯卡三角（法国数学家帕斯卡发现），在中国也称为杨辉三角（宋代数学家杨辉整理记载），是一个由数字构成的三角形阵列，在组合数学、概率论等领域有广泛应用。
设第 n 行（从 0 开始计数）第 k 列（从 0 开始计数）的数为 C(n, k)。它满足以下递推关系：
C(n, k) = C(n-1, k-1) + C(n-1, k)边界条件：
C(n, 0) = 1 (每行第一个数)
C(n, n) = 1 (每行最后一个数)这个公式的意义是：三角形中任意一个非边界位置的数，都等于它“肩膀”上两个数（上一行正上方和左上方）之和。
从组合数学的角度看，C(n, k) 正是组合数，表示从 n 个不同的元素中无序地选取 k 个元素的方案数。
C(n, k) = n! / (k! * (n-k)!)其中 '!' 表示阶乘 (例如 5! = 5×4×3×2×1)。
注意：在帕斯卡三角中，我们通常从第 0 行开始计数。
利用递推公式 C(n, k) = C(n-1, k-1) + C(n-1, k) 和边界条件 C(n, 0) = C(n, n) = 1，我们可以逐行生成任意指定行数的帕斯卡三角。
下面是使用 C++ `vector` 来生成帕斯卡三角前 `numRows` 行的核心代码片段。这种方法直接利用了递推关系。
// 函数：生成帕斯卡三角的前 numRows 行
// 返回一个二维向量，表示整个三角形
vector> generate(int numRows) {
vector> triangle; // 用于存储结果的二维向量
// 如果请求的行数为 0，则返回空三角形
if (numRows <= 0) {
return triangle;
}
// 逐行构建三角形
for (int i = 0; i < numRows; ++i) {
// 创建当前行，大小为 i+1，并用 1 初始化所有元素
// 因为 C(i, 0) 和 C(i, i) 总是 1
vector row(i + 1, 1);
// 计算当前行内部的元素 (从第 1 个到倒数第 2 个)
// j 从 1 开始，直到 row.size() - 2 (即 i - 1)
for (int j = 1; j < i; ++j) {
// 应用递推公式: C(i, j) = C(i-1, j-1) + C(i-1, j)
// triangle[i-1] 是上一行
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
// 将构建好的当前行添加到结果三角形中
triangle.push_back(row);
}
return triangle; // 返回完整的帕斯卡三角
} 注意：对于只需要计算某一行或某个特定组合数 C(n, k) 的情况，存在空间复杂度更优的 O(N) 或 O(k) 的算法（如下一页练习题所示）。
（下方将显示包含 C(n, k) 的帕斯卡三角部分）
二项式 (a + b)ⁿ 展开后的各项系数，恰好是帕斯卡三角的第 n 行（从第 0 行开始计数）。
(a + b)ⁿ = C(n,0)aⁿb⁰ + C(n,1)aⁿ⁻¹b¹ + C(n,2)aⁿ⁻²b² + ... + C(n,n)a⁰bⁿ在一个网格图中，从左上角 (0,0) 走到右下角 (m, n)，如果每次只能向右或向下移动一步，那么总共有多少条不同的路径？
答案是 C(m+n, m) 或 C(m+n, n)。这相当于在总共 m+n 步中选择 m 步向右（或 n 步向下）。
例如，从 (0,0) 到 (2,3)，共需 2+3=5 步，其中 2 步向右，3 步向下。路径数 = C(5, 2) = C(5, 3) = 10。
在进行 n 次独立的伯努利试验（每次试验只有成功/失败两种结果，成功概率为 p），恰好有 k 次成功的概率 P(X=k) 计算公式中包含组合数：
P(X = k) = C(n, k) * pᵏ * (1-p)ⁿ⁻ᵏ例如，抛掷一枚均匀硬币 5 次，恰好出现 2 次正面的概率 = C(5, 2) * (0.5)² * (0.5)³ = 10 * 0.25 * 0.125 = 0.3125。
请实现一个 C++ 函数 long long getCombination(int n, int k)，要求只使用 O(k) 或 O(min(k, n-k)) 的额外空间来计算并返回组合数 C(n, k) 的值。注意处理中间结果可能产生的溢出问题（使用 long long）。
提示：可以利用公式 C(n, k) = C(n-1, k-1) + C(n-1, k) 进行迭代，但只保留上一行的信息，或者利用乘法公式 C(n, k) = (n * (n-1) * ... * (n-k+1)) / k! 并优化计算顺序。
请实现一个 C++ 函数 void printPascalRow(int n)，要求在仅使用 O(1) 额外空间的条件下（不计算存储最终结果的打印输出空间），打印出帕斯卡三角的第 n 行（从第 0 行算起）。
提示：利用 C(n, k) = C(n, k-1) * (n - k + 1) / k 的关系式，可以在 O(n) 时间内计算并打印第 n 行的每个元素。
帕斯卡三角中的数值增长非常快。例如，C(30, 15) 就已经超过了 32 位整型 (int) 的最大值。当 n 稍大时（如 N > 30 左右），即使是 64 位整型 (long long 在 C++) 也可能溢出 (例如 C(67, 33) 就会溢出)。
解决方案：
long long 类型存储结果。// 示例：使用 long long
long long combination(int n, int k) {
if (k < 0 || k > n) return 0;
if (k == 0 || k == n) return 1;
if (k > n / 2) k = n - k; // 优化：利用 C(n,k) = C(n, n-k)
long long res = 1;
for (int i = 1; i <= k; ++i) {
// 优化乘除顺序防止中间溢出和保证整除
res = res * (n - i + 1) / i;
// 注意：这里需要严格证明 res * (n - i + 1) 不会溢出 long long
// 更安全的做法是先除以 gcd(res, i)，再乘 (n-i+1)，再除以 i/gcd(res,i)
// 或者直接使用大数库
}
return res;
}在计算 C(n, k) 时，务必确保输入满足基本条件：0 ≤ k ≤ n 且 n ≥ 0。对于非法输入（如 k < 0 或 k > n），应返回 0 或抛出异常。
如果需要频繁查询同一个 n 下的不同 k 对应的组合数，预先计算并存储帕斯卡三角的对应行（或整个三角，如果空间允许）会比每次独立计算 C(n, k) 更高效。
第 n 行的所有数字之和等于 2ⁿ。这对应于从 n 个元素中选取任意数量（0 到 n 个）元素的总方法数，即集合的幂集大小。
如果将帕斯卡三角中的奇数涂色、偶数留白，当行数足够多时，会形成一个著名的分形图案——**谢尔宾斯基三角 (Sierpinski Triangle)**。
将帕斯卡三角中的每个数对一个素数 p 取模，也会产生有趣的分形结构，这与 Lucas 定理相关。
沿对角线方向求和会得到**斐波那契数列 (Fibonacci Numbers)**。
卡特兰数 Cₙ 是一个重要的组合数列，出现在许多计数问题中（如合法括号序列、二叉树形态数、凸多边形三角剖分数等）。它与中心二项式系数有关：Cₙ = (1 / (n+1)) * C(2n, n)。
帕斯卡三角对应于二项式 (a+b)ⁿ 的展开系数。对于多项式 (a₁ + a₂ + ... + aₘ)ⁿ 的展开，其系数是多项式系数，可以看作是帕斯卡三角在高维的推广（帕斯卡棱锥/金字塔）。
帕斯卡三角的第 n 行是函数 (1+x)ⁿ 展开式的系数。利用生成函数是解决复杂组合计数问题的强大工具。
在动态规划或生成帕斯卡三角时，如果只需要当前行和上一行的数据，可以使用两个一维数组（或一个二维数组的两行）交替存储，将空间复杂度从 O(N²) 优化到 O(N)。
在需要大量计算组合数 C(n, k) mod P（P 为素数）的场景下，可以预先计算 0! 到 N! 的阶乘值及其模 P 的乘法逆元。这样，每次查询 C(n, k) mod P 只需要 O(1) 的时间，通过公式 C(n,k) = n! * inv(k!) * inv((n-k)!) mod P 计算。
帕斯卡三角蕴含着丰富的数学美和深刻的组合思想，值得进一步探索！