1 基礎知識

（一）
組合數$C_n^k$的計算公式，
$$C_n^k=\frac{n?(n?1)?(n?k+1)}{1?2?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 工程化

暫無。。。