求组合数
前置
组合数一般记为 \(C_a^b\)，表示从 \(a\) 个不同的物品中选择 \(b\) 个物品的方案数，且不计顺序。
例如 ，\(C_5^3\) 表示从 \(5\) 个物品中选择 \(3\) 个物品。假设 \(5\) 个物品分别编号为 \(1,2,3,4,5\)，那么可以进行如下选择：
- \(1,2,3\)
- \(1,2,4\)
- \(1,2,5\)
- \(1,3,4\)
- \(1,3,5\)
- \(1,4,5\)
- \(2,3,4\)
- \(2,3,5\)
- \(2,4,5\)
- \(3,4,5\)
共 \(10\) 种方案，也就是说 \(C_5^3 = 10\)。
1. 递推 \(\Theta(n^2)\)
数据范围 : \(T\le 10^4,b\le a\le 2 \times 10^3\)。
因为 \(C_a^b\) 表示从 \(a\) 个不同的物品中选择 \(b\) 个物品的方案数，那么我们将所有的选法分成两种情况。
首先随机挑出 \(1\) 个物品。
第一种情况，选完后包含这个物品，那么就需要再剩下的 \(a-1\) 个物品之中再选 \(b-1\) 个物品，即 \(C_{a-1}^{b-1}\)。
第二种情况，选完后不包含这个物品，那么就需要在剩下的 \(a-1\) 个物品中选 \(a\) 个物品，即 \(C_{a-1}^b\)。
因此可以得到递推式 \(C_a^b = C_{a-1}^{b-1} + C_{a-1}^b\)。
void init(){
for(int i=0; i<N; i++){
for(int j=0; j<=i; j++){
if(!j){
C[i][j] = 1;
}
else{
C[i][j] = add(C[i-1][j], C[i-1][j-1]);
}
}
}
}
2. 公式 \(\Theta(n \cdot \log_{2}{n})\)
数据范围 : \(T \le 10^ 4,b\le a \le 10^5\)。
求 \(C_n^m\) 的公式为 \(\dfrac{a!}{(a-b!) \cdot b!}\)，可以预处理出所有数的阶乘值 \(fact_i\) ，再利用公式解答。
其中算除以一个数的阶乘要变为乘它阶乘的逆元 \(infact_i\)，表示 \(i!\) 的逆元，也需要预处理。
因此，\(C_a^b = fact_a \times infact_{a-b} \times infact_b\)。
int fact[N]; // fact[i] 表示 i 的阶乘
int infact[N]; // infact[i] 表示 i! 的逆元
int fpm(int a, int b){ // 快速幂
int res = 1;
while(b){
if(b&1){
res = mul(res, a);
}
b >>= 1;
a = mul(a, a);
}
return res;
}
void init(){
fact[0] = infact[0] = 1;
for(int i=1; i<N; i++){
fact[i] = mul(fact[i-1] * i); // 求阶乘
infact[i] = mul(infact[i-1], fpm(i, mod - 2)); // 求逆元
}
}
int C(int a, int b){
return mul(fact[a], infact[b], infact[a-b]);
}
3. 卢卡斯定理 \(\Theta(\log_{p}{n} \cdot p \cdot \log_{2}{p})\)
数据范围 : \(T \le 20,b \le a \le 10^{18},p \le 10^5,p是质数\)。
转化
首先将 \(a\) 和 \(b\) 化成 \(p\) 进制，即
\(a = a_k \cdot p^k + a_{k-1} \cdot p^{k-1} + \dots + a_0 \cdot p^0\)
\(b = b_k \cdot p^k + b_{k-1} \cdot p^{k-1} + \dots + b_0 \cdot p^0\)
生成函数
\((1 + x)^p = C_p^0 \cdot x^0 + C_p^1 \cdot x^1 + C_p^2 \cdot x^2 + \dots + C_p^p \cdot x^p\)
因为 \(p\) 是质数，所以 \(p\) 不包含小于 \(p\) 的质因子，所以这些项都能整除 \(p\)。
所以，将中间的项消掉，就得到 \((1 + x)^p \equiv 1 + x^p \pmod p\)。
展开
把 \(a\) 带入到 \((1 + x)^p\) 中的 \(p\)，就可以得到
把内部的括号去掉，还可以得到
结论
\(C_a^b \equiv C_{a_k}^{b_k} \cdot C_{a_{k-1}}^{b_{k-1}} \dots C_{a_0}^{b_0} \pmod p\)。
\(C_a^b \equiv C_{a\mod p}^{b\mod p} \cdot C_{a/p}^{b/p} \pmod{p}\)。
int C(int a, int b){
if(b > a){
return 0;
}
int res = 1;
for(int i=1, j=a; i<=b; i++, j--){
// 相当于 res = res * j / i
res = mul(res, j);
res = mul(res, fpm(i, p-2));
}
return res;
}
int lucas(int a, int b){
if(a < p && b < p){
return C(a, b);
}
return mul(C(a%p, b%p), lucas(a/p, b/p));
}