【模板】组合数取模

1.利用递推式预处理组合数取模

题目描述

给定 $n$ 组询问，每组询问给定两个整数 $a,b$，请你输出 $C_a^{b}mod(10^9+7)$ 的值。

数据范围

$1\le n\le 10000$

$1\le b\le a\le 2000$

递推式

$$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$$

#include 
#include 

using namespace std;

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;
            }
        }
    }
}

int main()
{
    init();
    
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.预处理阶乘的余数和阶乘逆元的余数

题目描述

给定 $n$ 组询问，每组询问给定两个整数 $a,b$，请你输出 $C_a^{b}mod(10^9+7)$ 的值。

数据范围

$1\le n\le 10000$

$1\le b\le a\le 10^5$

逆元

若 $a\ast x\equiv 1(modb)$ 且 $a$ 与 $b$ 互质，那么我们就能定义 $x$ 为 $a$ 的逆元，记为 $a^{-1}$，所以我们也可以称 $x$ 为 $a$ 在 $modb$ 意义下的倒数。

因此，对于 $\frac{a}{b}(modp)$，我们就可以求出 $b$ 在 $modp$ 下的逆元，然后乘上 $a$，再 $modp$，就是这个分数的值了。

快速幂求逆元

这个做法要利用费马小定理，如下：

若 $p$ 为素数，$a$ 为正整数，且 $a$、$p$ 互质，则有 $a^{p-1}\equiv 1(modp)$。

可以发现这个式子右边刚好为 $1$，因此，代入原式即可得到：

$a\ast x\equiv 1(modp)$

$a\ast x\equiv a^{p-1}(modp)$

$x\equiv a^{p-2}(modp)$

所以我们可以用快速幂来算出 $a^{p-2}(modp)$ 的值，这个数就是它的逆元了。

组合数

$$C_a^b=\frac{a\ast (a-1)\ast ...\ast (a-b+1)}{b\ast (b-1)\ast ...\ast 1}=\frac{a!}{b!\ast (a-b)!}$$

首先，预处理阶乘的余数和阶乘逆元的余数：

$fact[i]=(i!)mod(10^9+7)$

$infact[i]=(i!{)}^{-1}mod(10^9+7)$

那么，组合数求解如下：

$C_a^b=fact[a]\ast infact[b]\ast infact[a-b]$

#include 
#include 

using namespace std;

typedef long long ll;

const int N = 100010, mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int b, int m)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    // 预处理阶乘的余数和阶乘逆元的余数
    fact[0] = 1, infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (ll)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

3.卢卡斯定理

题目描述

给定 $n$ 组询问，每组询问给定三个整数 $a,b,p$，其中 $p$ 是质数，请你输出 $C_a^{b}modp$ 的值。

数据范围

$1\le n\le 20$

$1\le b\le a\le 10^{18}$

$1\le p\le 10^5$

Lucas定理

若 $p$ 是质数，则对于任意整数 $1\le m\le n$ 有 $C_n^m\equiv C_{nmodp}^{mmodp}\ast C_{n/p}^{m/p}(modp)$。

#include 
#include 

using namespace std;

typedef long long ll;

// 快速幂模板
int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return res;
}

// 通过定义求组合数C(a, b)
int C(int a, int b, int p)
{
    if (b > a) return 0;
    
    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

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

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
        ll a, b;
        int p;
        scanf("%lld%lld%d", &a, &b, &p);
        printf("%d\n", lucas(a, b, p));
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

4.将组合数分解质因数+高精度乘低精度

题目描述

输入 $a,b$，求 $C_a^b$ 的值。注意结果可能很大，需要使用高精度计算。

数据范围

$1\le b\le a\le 5000$

思路

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用。

$$C_a^b=\frac{a\ast (a-1)\ast ...\ast (a-b+1)}{b\ast (b-1)\ast ...\ast 1}=\frac{a!}{b!\ast (a-b)!}$$

首先筛选出范围内的所有质数，然后将组合数分解质因数为 $p_1^{c_1}\ast p_2^{c_2}\ast ...\ast p_k^{c_k}$，最后用高精度乘法将所有质因子乘起来即可。

如何求 $n!$ 中有多少个质因子 $p$ 呢？

$$\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +...$$

#include 
#include 
#include 

using namespace std;

const int N = 5010;

int primes[N], cnt;
bool st[N];
int sum[N];

// 线性筛
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 求n!中有多少个质因子p
int get(int n, int p)
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}

// 高精度乘以低精度
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++)
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    
    get_primes(a);
    
    for (int i = 0; i < cnt; i++)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }
    
    vector<int> res;
    res.push_back(1);
    
    for (int i = 0; i < cnt; i++)
    {
        for (int j = 0; j < sum[i]; j++)
        {
            res = mul(res, primes[i]);
        }
    }
    
    for (int i = res.size() - 1; i >= 0; i--)
    {
        printf("%d", res[i]);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88