1.杨辉三角递推法求组合数

设 $C[i][j]$ 为已在 $i$个元素中抽取了 $j$ 个元素，对于上一步描述，有可能是：
这一步没有抽取元素，之前已经抽了 $j$ 个元素：$C[i-1][j]$
这一步抽取了一个元素，之前已经抽了 $j-1$ 个元素：$C[i-1][j-1]$
将这两种情况加起来便是 $C[i][j]$ 的结果，由此得出式子：
$C[i][j] = C[i-1][j] + C[i-1][j-1]$

时间复杂度：$O(n^2)$

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void getC(int N)
{
    for (int i = 0; i <= N; 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]) % p;
            }
        }
    }
}
$i\backslash j$ 0 1 2 3 4 5 6
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1

杨辉三角公式：

$C_{n}^{0} = C_{n}^{n} = 1$
$C_{n}^{m} = C_{n}^{n-m}$
$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$

计蒜客-T1984

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int C[N][N];
const int p = 1e9 + 7;
void getC(int N)
{
    for (int i = 0; i <= N; 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]) % p;
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    getC(n);
    cout << C[n][m] << '\n';
    return 0;
}

2.快速幂和乘法逆元求组合数

递推法 $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$ 会 TLE
考虑用 $C_{n}^{m} = \dfrac{n!}{m!(n-m)!}$ 直接计算。
用 $f[x]$ 存 $x! \pmod{p}$ 的值，
用 $g[x]$ 存 $\dfrac{1}{x!} \pmod{p}$ 的值。
因为 $p$ 是质数且 $n,m$ 都小于 $p$，即 $n, m$ 与 $p$ 互质，
所以根据费马小定理 $a \cdot a^{p-2} \equiv 1 \pmod{p}$，
$g[i] = \dfrac{1}{i!} \pmod{p} = \dfrac{1}{i} \times \dfrac{1}{(i-1)!} \pmod{p} = \text{qpow}(i,p-2) \times g[i-1]$
查询 $C_{n}^{m} \pmod{p} = f[n] \cdot g[n-m] \cdot g[m] \pmod{p}$

时间复杂度：$O(n \log p)$

核心代码

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
int qpow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
void init(int n)
{
    f[0] = g[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] * i % p;
        g[i] = g[i - 1] * qpow(i, p - 2) % p;
    }
}
int getC(int n, int m)
{
    return f[n] * g[m] % p * g[n - m] % p;
}

3.Lucas定理求组合数

$C_{n}^{m} \equiv C_{n/p}^{m/p} \cdot C_{n \bmod p}^{m \bmod p} \pmod{p}$
引理1：$C_{p}^{x} \equiv 0 \pmod{p}$, $0<x<p$
因 $C_{p}^{x} = \dfrac{p!}{x!(p-x)!} = \dfrac{p(p-1)!}{x(x-1)!(p-x)!} = \dfrac{p}{x} \cdot C_{p-1}^{x-1}$
故 $C_{p}^{x} \equiv p \cdot \text{inv}(x) \cdot C_{p-1}^{x-1} \equiv 0 \pmod{p}$
引理2：$(1+x)^p \equiv 1 + x^p \pmod{p}$
由二项式定理 $(1+x)^p = \sum\limits_{i=0}^{p} C_{p}^{i} x^i$
由引理1知，只剩下i=0,p这两项，得证

时间复杂度：$O(p \log p + \log_p n)$

核心代码

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
int qpow(int a, int b, int p)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
void init(int p)
{
    f[0] = g[0] = 1;
    for (int i = 1; i <= p; i++)
    {
        f[i] = f[i - 1] * i % p;
        g[i] = g[i - 1] * qpow(i, p - 2, p) % p;
    }
}
int getC(int n, int m, int p)
{
    return f[n] * g[m] * g[n - m] % p;
}
int Lucas(int n, int m, int p)
{
    if (m == 0)
    {
        return 1;
    }
    return Lucas(n / p, m / p, p) * getC(n % p, m % p, p) % p;
}

4.高精度加线性筛求组合数（不取模）

分解质因数：$C_{n}^{m} = p_1^{m_1} \cdot p_2^{m_2} \cdot \cdots \cdot p_k^{m_k}$
其中 $p_1$-$p_k$ 是 $[1,n]$ 中的素数；
$m_1$~$m_k$ 是其中对应的每个素数的次数，是在 $n!$ 中的次数减去 $m!$ 中的次数再减去 $(n-m)!$ 中的次数；
$n!$ 中 $p$ 的个数：$s = \left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \left\lfloor \dfrac{n}{p^3} \right\rfloor + \cdots$

image-20221215190711847

AcWing 888. 求组合数 IV

题目描述

输入 $n,m$，求 $C_{n}^{m}$ 的值。
注意结果可能很大，需要使用高精度计算。

输入格式

共一行，包含两个整数n和m。

输出格式

共一行，输出$C_{n}^{m}$的值。

数据范围

1≤m≤n≤5000

输入样例：

1
5 3

输出样例：

1
10

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int primes[N], vis[N], cnt;
int C[N];
void get_primes(int n)
{ // 筛素数
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            primes[cnt++] = i;
        }
        for (int j = 0; i * primes[j] <= n; j++)
        {
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
}
int get(int n, int p)
{ // n!中p的个数
    int s = 0;
    while (n)
    {
        s += n / p, n /= p;
    }
    return s;
}
int getps(int n, int m, int p)
{ // C中p的个数
    return get(n, p) - get(m, p) - get(n - m, p);
}
void mul(int C[], int p, int &len)
{ // 高精度
    int t = 0;
    for (int i = 0; i < len; i++)
    {
        t += C[i] * p;
        C[i] = t % 10;
        t /= 10;
    }
    while (t)
    {
        C[len++] = t % 10;
        t /= 10;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    get_primes(n);
    int len = 1;
    C[0] = 1;
    for (int i = 0; i < cnt; i++)
    {
        int p = primes[i];
        int s = getps(n, m, p);
        while (s--)
        {
            mul(C, p, len);
        }
    }
    for (int i = len - 1; i >= 0; i--)
    {
        cout << C[i];
    }
    cout << '\n';
    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
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[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;
            }
        }
    }
}
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 n, m;
    cin >> n >> m;
    get_primes(n);
    for (int i = 0; i < cnt; i++)
    {
        int p = primes[i];
        sum[i] = get(n, p) - get(n - m, p) - get(m, 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--)
    {
        cout << res[i];
    }
    cout << '\n';
    return 0;
}