组合计数

本章主要记录基础组合数学的有关知识，包括加法原理、乘法原理、排列组合、二项式定理、卢卡斯定理等基本知识。

一、计数原理

基础的计数原理包括加法原理和乘法原理，是组合数学的基础。

1.1$\quad$加法原理

若完成一件事情的方法有 $n$ 类，其中第 $i$ 类方法有 $a_i$ 种不同的方法，且这些方法互补重合，则完成这件事一共有 $\sum_{i=1}^na_i$ 种不同的方法。这样的计数原理称为加法原理。

例$\qquad$中午可以去A、B、C三个街区吃饭，三个街区分别有 $6$、$5$、$8$ 家餐厅，那么中午吃饭有 $6+5+8=19$ 家餐厅可选。

1.2$\quad$乘法原理

若完成一件事情需要 $n$ 个步骤，其中第 $i$ 个步骤有 $a_i$ 种不同的完成方法，且这些步骤互不干扰，则完成这件事一共有 $\prod_{i=1}^na_i$ 种不同的方法。这样的计数原理成为乘法原理。

例$\quad$餐厅有 $4$ 种主食，$2$ 种配菜，$5$ 种配汤，那么可以组成 $4\times2\times5=40 $ 种套餐。

二、排列数与组合数

2.1$\quad$排列数

从 $n$ 个不同元素种依次选出 $m$ 个元素排成一列，产生的不同的排列的数量为

2.2$\quad$组合数

从 $n$ 个不同元素种依次选出 $m$ 个组成一个集合（不考虑顺序），产生的不同的集合的数量为

2.3$\quad$组合恒等式

恒等式1$\quad$ 选出一部分再反选，有 $\dbinom{n}{k}=\dbinom{n}{n-k}$。

恒等式2$\quad$ 考虑枚举是否选第 $1$ 个，有 $\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$。

恒等式3$\quad\dbinom{n}{k}\dbinom{k}{t}=\dbinom{n}{t}\dbinom{n-t}{k-t}$。

$\qquad$辅助理解：$n$ 个人选 $k$ 个队长再在其中选 $t$ 个大队长，等于 $n$ 个人选 $t$ 个大队长再在剩下 $n-t$ 个选 $k-t$ 个队长。

恒等式4$\quad$ 枚举最后一个选在哪里，也可由恒等式1迭代导出，有 $\dbinom{n}{k}=\sum\limits_{i=k}^n\dbinom{i-1}{k-1}$。

恒等式5$\quad$ $n+m$ 个选 $k$ 个，枚举前 $n$ 个选多少，有 $\dbinom{n+m}{k}=\sum\limits_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}$。

恒等式6$\quad$ 枚举第 $a+1$ 个位置，有 $\dbinom{n}{a+b+1}=\sum\limits_{i=a+1}^{n-b}\dbinom{i-1}{a}\dbinom{n-i}{b}$。

$b=0$ 时退化为恒等式4。

恒等式7$\quad$ $\sum\limits_{i=0}^n\dbinom{n}{i}=2^n$。

2.4$\quad$组合数的求法

2.4.1 $\quad$ 根据定义求解

求解 $C_n^m\bmod p$ 时，可以计算 $n!\bmod p$ 的值，之后乘上 $m!^{-1}(n-m)!^{-1}\bmod p$ （即逆元）即可。当 $p$ 为质数时可以利用欧拉定理和快速幂求解逆元，其余情况可以线性求解逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
ll qpow(ll a,ll b,ll p){
    ll w=1;
    while(b){
        if(b&1) w=w*a%p;
        a=a*a%p;
        b>>=1;
    }
    return w;
}
ll C(ll n,ll m,ll p){
    if(m>n) return 0;
    return (a[n]*qpow(a[m],p-2,p)%p)*qpow(a[n-m],p-2,p)%p;//a数组为线性预处理的阶乘数组
}

2.4.2 $\quad$ 递推求解

根据组合恒等式 2

我们可以递推求解。下面的代码求解出了所有 $\dbinom{i}{j}(0\leq j\leq i\leq n)$，表示为数组 c[i][j]。

1
2
3
4
5
6
7
8
9
void solve(int n){
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}

三、二项式定理与杨辉三角

3.1$\quad$二项式定理

例 $\quad$ $(a+b)^3=a^3+3a^2b+3ab^2+b^3$。

3.2$\quad$杨辉三角

对于每个 $n$，二项式定理拆解后的二项式稀疏构成杨辉三角，如下图。

可以发现，三角中每一个数为其左上和右上的两个数之和，可以得出 $C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}$，即恒等式 2。

四、卢卡斯定理

4.1$\quad$卢卡斯定理

卢卡斯定理$\quad$若 $p$ 是质数，则对于任意整数 $1\leq m\leq n$，有：

求解 $\binom{n}{m}\bmod p$ 时，可以利用公式求解 $\dbinom{n\bmod p}{m\bmod p}\bmod p$，同时递归求解 $\dbinom{n/p}{m/p}\bmod p$，需要预处理出阶乘数组 $a$，在计算 $\dfrac{n!}{m!(n-m)!}$ 时利用逆元求出。因为 $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
28
29
30
31
32
33
#include<iostream>
using namespace std;
typedef long long ll;
#define MAXN 100005
ll t,a[MAXN];
ll qpow(ll a,ll b,ll p){
    ll w=1;
    while(b){
        if(b&1) w=w*a%p;
        a=a*a%p;
        b>>=1;
    }
    return w;
}
ll C(ll n,ll m,ll p){
    if(m>n) return 0;
    return (a[n]*qpow(a[m],p-2,p)%p)*qpow(a[n-m],p-2,p)%p;
}
ll lucas(ll n,ll m,ll p){
    if(m==0) return 1;
    return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
int main(){
    ll n,m,p;
    cin>>t;
    while(t--){
        cin>>n>>m>>p;
        a[0]=1;
        for(int i=1;i<=p;i++) a[i]=a[i-1]*i%p;
        cout<<lucas(n+m,m,p)<<endl;
    }
    return 0;
}

4.2 扩展卢卡斯定理

此部分需要同余基础知识点，貌似与卢卡斯定理没有任何关系。

因为利用卢卡斯定理处理问题存在局限性（$p$ 必须为质数），不能处理普遍情况。此时可以用扩展卢卡斯定理解决普遍情况。

求解以下问题：对于组合数 $\dbinom{n}{m}$ ，求 $\dbinom{n}{m}\bmod p$ ，$p$ 不保证为质数。

如果 $p$ 为质数会方便很多，所以考虑将其拆为若干个模质数的式子。根据唯一分解定理，

所以考虑拆分为

因为 $\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}$ ，在模 $p_1^{a_1}$ 意义下不能直接利用逆元化解分母。所以考虑如下拆分：

$x$ 为 $n!$ 中包含的 $p$ 的因子个数，$y$、$z$ 同理。

考虑逐个解决。因为 $n!$ 中一共有 $\left\lfloor\dfrac{n}{p}\right\rfloor$ 个数是 $p$ 的倍数，然后递归处理其他因数。

将 $\prod\limits_{i=1,i\not\equiv0\pmod p}^{n}i$ 拆分为两个部分：不含有 $p$ 的因子和含有 $p$ 的因子。

所以考虑设立函数 $f(n)=\dfrac{n!}{p^k}$，所以有

边界：$f(0)=1$。

这样函数 $f$ 就一定和 $p^k$ 互质了，就可以直接利用扩展欧几里得算法（$\text{exgcd}$）求出逆元（ $\text{inv}$ ），化分母。

然后还需要求解 $p^{x-y-z}$。考虑设立函数 $g(n)=x$（ $x$ 为 $n!$ 中包含的 $p$ 的因子数），所以有

边界：$g(x)=0(x<p)$

这样就可以求解啦。式子变成了

然后用中国剩余定理（ $\text{CRT}$ ）合并即可。

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
#include<iostream>
using namespace std;
#define MAXN 10005
typedef long long ll;
ll n,m,P,A[MAXN],B[MAXN];
ll qpow(ll a,ll b,ll p){
    ll w=1;
    while(b){
        if(b&1) w=w*a%p;
        a=a*a%p;
        b>>=1;
    }
    return w;
}
ll f(ll x,ll p,ll pk){
    if(x==0) return 1;
    ll a=1,b=1;
    for(ll i=1;i<=pk;i++){
        if(i%p) a=a*i%pk;
    }
    a=qpow(a,x/pk,pk);
    for(ll i=pk*(x/pk);i<=x;i++){
        if(i%p) b=b*(i%pk)%pk;
    }
    return f(x/p,p,pk)*a%pk*b%pk;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
ll inv(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
ll g(ll x,ll p){
    if(x<p) return 0;
    return x/p+g(x/p,p);
}
ll CmodPk(ll p,ll pk){
    ll fx=f(n,p,pk),fy=f(m,p,pk),fz=f(n-m,p,pk);
    fy=inv(fy,pk),fz=inv(fz,pk);
    return fx*fy%pk*fz%pk*qpow(p,g(n,p)-g(m,p)-g(n-m,p),pk)%pk;
}
ll crt(ll cnt){
    ll ans=0;
    for(ll i=1;i<=cnt;i++){
        ll M=P/A[i];
        ll T=inv(M,A[i]);
        ans=(ans+B[i]*M%P*T%P)%P;
    }
    return ans;
}
ll exlucas(){
    ll tmp=P,cnt=0;
    for(ll i=2;i*i<=P;i++){
        if(tmp%i==0){
            ll pk=1;
            while(tmp%i==0) pk*=i,tmp/=i;
            A[++cnt]=pk;
            B[cnt]=CmodPk(i,pk);
        }
    }
    if(tmp>1){
        A[++cnt]=tmp;
        B[cnt]=CmodPk(tmp,tmp);
    }
    return crt(cnt);
}
int main(){
    cin>>n>>m>>P;
    cout<<exlucas();
    return 0;
}