小花生

study & life record.

组合数

发表于 分类于 ，

不同数据范围中组合数的求法。

总结求 $C_a^b\ (\mathrm{mod}\ p)$ 的方法。

递推法

适用于 a, b 较小的情况。

利用 $C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$ 进行递推。

1
2
3
4
5
6
7
8
9
10
11
const int N = 2010, mod = 1e9 + 7;
int C[N][N];

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] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }   
}

阶乘预处理

适用于 a, b 较大的情况。

$\displaystyle C_a^b = \frac{a!}{b!(a-b)!}$

预处理 阶乘fact 和 阶乘的逆元infact。

那么$\displaystyle C_a^b= fact[a] \times infact[b] \times infact[a-b]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

void init(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

// C_a^b 表示为
fact[a] * infact[b] % mod * infact[a - b] % mod;

Lucas定理处理

适用于 a, b 超级大的情况。

Lucas定理：

$\displaystyle C_a^b \equiv C_{a\ \mathrm{mod}\ p}^{b\ \mathrm{mod}\ p}\times C_{a/p}^{b/p}\ (\mathrm{mod}\ p)$

1
2
3
4
5
6
7
8
int C(int a, int b){
    return fact[a] * infact[b] % p * infact[a - b] % p;
}

int lucas(int a, int b){
    if(a < p && b < p) return C(a, b);
    return C(a % p, b % p) * lucas(a / p, b / p) % p;
}