数论补完计划 Part5 组合计数

排列数与组合数#

排列组合基础#

对于一个正整数，它的阶乘等于，记作。特殊地，。

小学时我们就知道，用三个数字最多能表示出个互不相同的三位数字；若改为组成四位数，那么答案就该是种。这其实就是排列数的一个经典应用。探究这个答案是怎么得到的——对于第一个位置，可以有种填数方法；对于第二个位置，因为先前已经用掉一个数了，此时可选的数就只剩个，根据分步乘法原理，就应该乘上，以此类推……我们会惊奇地发现答案其实就是，或者可以表示成。

排列数是指从个物体中选出个并进行排列的总方案数。公式为。排列所隐含的意思是，选中的个物品之间是存在顺序差别的。例如上例选数字，和显然是不相同的两个数字，因此需要用到排列数。这也是它和组合数最大的差别。

上了高中，我们又知道，从个人中选出个人组队，总共能有种组队方案。答案是吗？鉴于一队和一对是等价的，那么其实队内的排序是不必要的，考虑到两个人能变出种排序，意味着同一个方案会出现两次，答案其实是。

组合数（或者用二项式表示法表示为）是指从个物体里选出个并进行组合的总方案数。公式为。它和排列数一样，只要均为正整数，那么结果也都是整数。特殊地，。组合蕴含的意思是，不考虑选中元素之间的顺序关系，正如选择组成一组和选择成一组是完全等价的。

记不住组合数公式的看这张图：

还有特殊情况，例如，当且时，我们规定计算结果是。

一个重要的恒等式是：。可以套公式验证。

排列组合扩展#

比如说二项式定理，这个非常的好用，尤其是当你需要计算的时候。二项式定理说道，对于的展开形式，我们可以通过公式：

来快捷得到。注意从开始。时我们很熟悉，完全平方展开，系数分别是；还好，系数为；时就是。很容易发现这个系数似乎关于中间那一项左右对称，这一点可以用恒等式完美解释。

跟二项式定理密切联系的还有一个杨辉三角，它长这个样子：

发现所有的二项式系数都可以在对应行找到。因此可以说，杨辉三角第行的第个数其实就对应组合数。再次仔细观察，可以发现当前的数字可以由它肩上的两个数字相加得到，例如，于是所有的组合数都可以由这个递推式得到：。

杨辉三角还有许多有趣的性质，例如将第行的所有二项式系数加起来能得到，要证明也很简单，利用二项式定理代入特值，这样就会得到。还有，你还可以从第行开始，将杨辉三角中的数按特定规则相加，就可以得到斐波那契数列的项，见下图：

即。可以在了解组合数递推公式的基础上理解这个规律。

Lucas 定理#

用于组合数取模问题，公式其实很简洁：

其中为质数（~~暗示扩展~~），除法为整除。而当时，第一项可以通过递归这个公式得到。

如果考虑递归，我们其实发现它和进制分解蛮像。事实上，定理就可以看作是在进制下进行对位求组合数的结果之积。也就是说，假如的进制表示分别为和（不存在对应为则为），那么。证明略（不会）。它经常和数位DP放在一起考。

虽然它简化了计算，但是它本质上还是需要计算组合数的值。因此需要维护模意义下的阶乘和阶乘的逆元，或者你还可以暴力求解，适用于模数易变的情况。

1
// 暴力求解组合数
2
int C(int n, int m, int p) {
3
    int res = 1;
4
    for (int i = 1, j = n; i <= m; i++, j--) {
5
        res = ((ll) res % p * j % p * inv(i, p) % p) % p;
6
    }
7
    return res;
8
}
9

10
int lucas(int n, int m, int p) {
11
    if (m > n) return 0; // 必须特判，否则 RE+WA
12
    if (n < p && m < p) return C(n, m, p) % p;
13
    return (lucas(n / p, m / p, p) % p * lucas(n % p, m % p, p) % p) % p;
14
}

1
// 预处理
2
int lucas(int n, int m, int p) {
3
    if (n < m) return 0; // 必须特判
4
    if (n < p && m < p) return (fac[n] % p * infac[m] % p * infac[n - m] % p) % p;
5
    return (lucas(n / p, m / p, p) % p * lucas(n % p, m % p, p) % p) % p;
6
}
7

8
void init(int lim) {
9
    fac[0] = infac[0] = 1;
10
    for (int i = 1; i <= lim; i++) {
11
        fac[i] = (fac[i - 1] * i % p) % p;
12
        infac[i] = (infac[i - 1] * inv(i, p) % p) % p;
13
    }
14
}

无论你选用哪一种，都不要忘了对特殊情况的特判，例如的答案应为。

扩展 Lucas 定理#

~~回收伏笔~~

既然定理只适用于为质数，何不把模数拆成质数呢？根据算术基本定理，这是可以做到的，假设最终分解为。我们把代求的组合数当作一个未知数，联立可以得到方程组：

发现可以使用朴素的中国剩余定理合并（不同质数之间显然互质），前提是我们得知道的值。

根据组合数的阶乘定义式得到：。但是还不能直接算，万一逆元不存在（或）怎么办？既然导致无解的原因是出现了的倍数，那么我们就把因子拆除了！设分别为中因子的个数，那么原问题可以变为求解：

此时因为除去了因子，逆元就可以放心求解了。此时还面临一个问题，即形如的算式的快速求解。分母可以用逆元求，其实时间复杂度瓶颈还是在阶乘取模上，因此只需要解决即可。我们从一个实例来感受如何求解：

例 3.1

求解的值

即。我们先写阶乘，再把的倍数提出来：

Undefined control sequence \textcolor

发现原式分为三个部分：的次幂、的阶乘和与互质的数的乘积。对于第二部分，由于可能仍然存在的倍数，故递归求解；对于第三部分，有一个很好的性质——把互质的数按个一组分下去（余下的另算），发现每个完整组的乘积模的值是相同的，故快速幂解决，最后暴力乘上剩下的即可。

假设每一个完整组的乘积模的值均为，剩余组模出来的值为，那么可以得到：

递归的下一层就是求解的值。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
typedef long long ll;
5
typedef pair<ll, ll> Equation;
6

7
ll exgcd(ll a, ll b, ll &x, ll &y) {
8
    if (!b) {
9
        x = 1, y = 0;
10
        return a;
11
    }
12
    ll d = exgcd(b, a % b, y, x);
13
    y -= a / b * x;
14
    return d;
15
}
16

17
ll inv(ll a, ll p) {
18
    ll ans, tmp;
19
    exgcd(a, p, ans, tmp);
20
    return (ans % p + p) % p;
21
}
22

23
ll qmul(ll a, ll b, ll p) {
24
    ll res = 0;
25
    while (b) {
26
        if (b & 1) res = (res + a) % p;
27
        a = (a + a) % p;
28
        b >>= 1;
29
    }
30
    return res % p;
31
}
32

33
ll qpow(ll a, ll b, ll p) {
34
    ll res = 1;
35
    while (b) {
36
        if (b & 1) res = (res % p * a % p) % p;
37
        a = (a * a) % p;
38
        b >>= 1;
39
    }
40
    return res % p;
41
}
42

43
ll mul(initializer_list<ll> args, ll p) {
44
    // 很方便的变长参数列表求连乘，int128 防止爆范围
45
    __int128 res = 1;
46
    for (ll i: args) {
47
        res = (res % p * i % p) % p;
48
    }
49
    return (ll) (res % p);
50
}
51

52
ll CRT(vector<Equation> &v) {
53
    // 中国剩余定理部分
54
    ll M = 1;
55
    ll res = 0;
56
    for (Equation eq: v) M *= eq.second;
57
    for (Equation i: v) {
58
        ll Mi = M / i.second;
59
        res = (res + qmul(qmul(i.first, Mi, M), inv(Mi, i.second), M)) % M;
60
    }
61
    return res % M;
62
}
63

64
ll resolve(ll a, ll p, ll ppow) {
65
    // 递归过程求解，即实现例3.1
66
    if (!a) return 1; // 1的阶乘模质数当然无论如何都是1
67
    ll s = 1;
68
    for (ll i = 1; i <= ppow; i++) {
69
        if (i % p) s = mul({s, i}, ppow); // 完整组循环节连乘
70
    }
71
    s = qpow(s, a / ppow, ppow); // 对完整组的积求幂
72
    for (ll i = a / ppow * ppow + 1; i <= a; i++) {
73
        if (i % p) s = mul({s, i}, ppow); // 对不完整组求积
74
    }
75
    return mul({s, resolve(a / p, p, ppow)}, ppow); // 递归过程
76
}
77

78
ll getA(ll n, ll m, ll p, ll ppow) {
79
    // 获取 CRT 方程组中的 a
80
    ll x = 0, y = 0, z = 0;
81
    // 统计 n, m, n - m 分别是 p 的多少次幂
82
    for (ll i = n; i; i /= p) x += i / p;
83
    for (ll i = m; i; i /= p) y += i / p;
84
    for (ll i = n - m; i; i /= p) z += i / p;
85
    // 套公式
86
    return mul({
87
        qpow(p, x - y - z, ppow),
88
        resolve(n, p, ppow),
89
        inv(resolve(m, p, ppow), ppow),
90
        inv(resolve(n - m, p, ppow), ppow)
91
    }, ppow);
92
}
93

94
ll exLucas(ll n, ll m, ll p) {
95
    // 分解质因数
96
    vector<Equation> E;
97
    for (ll i = 2; i * i <= p; i++) {
98
        if (p % i == 0) {
99
            // 统计对应质数以及它的幂
100
            ll c = 1;
101
            while (p % i == 0) {
102
                c *= i;
103
                p /= i;
104
            }
105
            E.emplace_back(getA(n, m, i, c), c);
106
        }
107
    }
108
    if (p > 1) E.emplace_back(getA(n, m, p, p), p); // 最后一个质数
109
    return CRT(E);
110
}
111

112
int main() {
113
    ios::sync_with_stdio(false);
114
    cin.tie(nullptr);
115
    cout.tie(nullptr);
116

117
    ll n, m, p;
118
    cin >> n >> m >> p;
119
    cout << exLucas(n, m, p) << endl;
120

121
    return 0;
122
}

其中 getA(n, m, p, ppow) 用来求解，即中国剩余定理中的； resolve(a, p, ppow) 实现求解。

Lucas 定理的实际应用#

鉴于定理在进制分解上的性质，它其实可以跟一些涉及到进制的算法放在一起考。例如数位DP，数位DP相关内容请见：记忆化搜索数位DP。

洛谷 P7976 [Stoi2033] 园游会#

题目地址：P7976

题目难度：提高+/省选-

设，给定，求：
对取模。
对于的数据，。

根据定理，我们知道。那怎么把这个用到函数上呢？我们可以发现，满足，即积性函数。

我们把转为三进制，那么此时求就可以通过按位算组合数并连乘得到。固定一个，此时对于的每一位，有几种可能：

，保证的情况下，，此时贡献为
，只能枚举，贡献为
，此时，贡献为

因此，真正能对答案产生实质性贡献的就是的情况。换句话说，当在内枚举时，我们只需要统计取不同值时（三进制下）位的个数即可，也就是标准的数位DP求解内数在三进制下总共有多少个。记结果为，那么答案就是。

洛谷 P6669/BZOJ 4737 [清华集训2016] 组合数问题#

题目地址：P6669

题目难度：省选/NOI-

题目来源：清华集训 2016

给定和，对于所有的有多少对满足是的倍数。答案对取模。
对于的测试点，，，且是一个质数。

读题，倍数必定满足关系。根据定理的基数对位组合求积意义，我们可以把都转成进制，并且，只要在连乘式中出现任意一个及以上的项，整个结果就是，也即的倍数。根据组合数的计算公式，发现只要满足，那么结果就是。

布尔型维护当前是否已经存在项。此时考虑同时填两个不同数的相同位置，也就是一次性填两个数，自然需要用到双层循环。鉴于题目要求，我们不仅需要维护是否顶到上界，还要额外维护是否顶到上界和上界。总的状态数是，转移是双层循环的，时间复杂度约为，完全足够。

Note

题解同步于本站

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

数论补完计划 Part5 组合计数

排列数与组合数#

排列组合基础#

排列组合扩展#

Lucas 定理#

扩展 Lucas 定理#

Lucas 定理的实际应用#

洛谷 P7976 [Stoi2033] 园游会#

洛谷 P6669/BZOJ 4737 [清华集训2016] 组合数问题#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

数论补完计划 Part5 组合计数

排列数与组合数#

排列组合基础#

排列组合扩展#

Lucas 定理#

扩展 Lucas 定理#

Lucas 定理的实际应用#

洛谷 P7976 [Stoi2033] 园游会#

洛谷 P6669/BZOJ 4737 [清华集训2016] 组合数问题#

支持与分享

评论区

音乐

目录

JustPureH₂O