组合数公式

• $C_a^b = \frac{a \times (a-1) \times … \times (1-b+1)}{1 \times 2 \times … \times b} = \frac{a!}{b! \times (a-b)!} \quad(1)$
• $C_a^b = C_{a-1}^b + C_{a-1}^{b-1} \quad(2)$

求法1.根据公式(2)递推

• 代码模板

for(int i = 0; i < c.length; i++){
    for(int j = 0; j <= i; j++){
        if(j == 0) c[i][j] = 1;
        else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
    }
}

求法2.根据公式(1)预处理阶乘

• $\frac{a}{b} (mod \ p) \not= \frac{a(mod \ p)}{b(mod \ p)}$，除法不好取整，所以应该用乘法对逆元进行运算来取代除法求值

• 代码模板

//由于1e9+7为质数，可以使用费马小定理，所以可以用快速幂求逆元，利用乘法代替除法
int mod = (int)1e9+7;

//快速幂模板
long qmi(long a, long k, long p){
    long res = 1;
    while(k != 0){
        if((k & 1) == 1) res = (res * a) % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

//fact[i]表示i! % mod 的值
//infact[i]表示i! % mod的逆元，用乘逆元来表示除法
for(int i = 1; i < N; i++){
    fact[i] = fact[i-1] * i % mod;
    infact[i] = qmi(fact[i], mod-2, mod) % mod;
}

//组合数为：fact[a] * infact[a-b] % mod * infact[b] % mod