二项式，排列组合，杨辉三角

二项式

---

二项式定理

排列组合

---

排列

公式：A(n,k) = n! / (n-k)! = n × (n-1) × ... × (n-k+1)

代码：

long perm(int n, int k) {
    long r = 1;
    for (int i = 0; i < k; i++) r *= n - i;
    return r;
}

隐含前提

• n ≥ 0，0 ≤ k ≤ n

• n ≤ 12 安全, n ≥ 13 必须用 long

组合

公式：C(n,k) = n! / (k! × (n-k)!) = A(n,k) / k!

代码：

long comb(int n, int k) {
    if (k > n - k) k = n - k;
    long r = 1;
    for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;
    return r;
}

隐含前提

• n ≥ 0，0 ≤ k ≤ n

• n ≤ 33 基本安全, n ≥ 34 必须用 long

杨辉三角

---

题链：洛谷 P1118

3   1   2   4
  4   3   6
    7   9
     16

原理

使用杨辉三角第 N-1 行（从第 0 行开始）对 N 个初始数字加权求和，能够直接得到最终数

示例：4 个初始数字 3、1、2、4 对应的杨辉三角第 3 行为 1 3 3 1，加权求和为：

3 * 1 + 3 * 1 + 3 * 2 + 1 * 4 = 16

参考

---

https://zhuanlan.zhihu.com/p/366287107

https://www.bilibili.com/video/BV1b1421k7ti