acwing算法基础之数学知识--求组合数基础版

1 基础知识

（一）
组合数$C_n^k$的计算公式，
$$C_n^k=\frac{n\cdot (n-1)\cdots (n-k+1)}{1\cdot 2\cdots k}$$
注意需要满足$k\le n$。
将上述公式转换为代码，如下所示，

int compute_combination_n_k(int n, int k) {if (k > n) {return -1; //-1表示无效值。}long long a = 1;//表示分子long long b = 1;//表示分母for (int i = 1; i <= k; ++i) {a = a * (n - i + 1); //注意这一步可能会超出long long最大值b = b * i;}long long res = a / b;return res;
}

上述代码在计算分子时比较容易超出long long，一般不采取这种计算方法，除非n比较小。

（二）
组合数的递推公式，
$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$$
注意需要满足$k\le n$。

利用该公式可以在$O(n)$时间复杂度下求出N以内的所有组合数，代码如下，

const int N = 2010;
int c[N][N];for (int i = 0; i < N; ++i) {for (int j = 0; j <= i; ++j) {if (!j) {c[i][j] = 1;} else {c[i][j] = c[i-1][j-1] + c[i-1][j];}}
}

使用上述计算方法，一般不会超出long long范围。

2 模板

暂无。。。

3 工程化

暂无。。。