跳转至

组合数

概述

排列数

从\(n\)个不同元素，任取\(m(m≤n,n,m均为自然数)\)个元素按照一定的顺序排成一列，叫做从\(n\)个不同元素中取出\(m\)个元素的一个排列；从\(n\)个不同元素中取出\(m(m≤n)\)个元素的所有排列的个数，叫做从\(n\)个不同元素中取出\(m\)个元素的排列数，用符号\(A_n^m(或者是P_n^m)\)表示。 \(A_n^m=\frac{n!}{(n-m)!}\)

组合数

从\(n\)个不同元素中，任取 \(m(m≤n)\)个元素组成一个集合，叫做从\(n\)个不同元素中取出\(m\)个元素的一个组合；从\(n\)个不同元素中取出\(m(m≤n)\)个元素的所有组合的个数，叫做从\(n\)个不同元素中取出\(m\) 个元素的组合数。用符号\(C_n^m\)来表示,组合数也常用\((_m^n)\)表示 \(C_n^m=\frac{n!}{m!(n-m)!}\)

各种排列

Note

(摘自oiwiki)

不相邻的排列

\(1-n\)这\(n\)个自然数中选\(k\)个，这\(k\)个中任何两个数都不相邻的组合有\((\frac{n-k+1}{k})\)

错位排列

我们把错位排列问题具体化，考虑这样一个问题：

\(n\)封不同的信，编号分别是\(1,2,3,4,5\)，现在要把这五封信放在编号\(1,2,3,4,5\)的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设我们考虑到第\(n\)个信封，初始时我们暂时把第\(n\)封信放在第\(n\)个信封中，然后考虑两种情况的递推：

前面\(n-1\)个信封全部装错； 前面\(n-1\)个信封有一个没有装错其余全部装错。 对于第一种情况，前面\(n-1\)个信封全部装错：因为前面\(n-1\)个已经全部装错了，所以第n封只需要与前面任一一个位置交换即可，总共有\(f(n-1)×(n-1)\)种情况。

对于第二种情况，前面\(n-1\)个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若\(n-1\)个信封中如果有一个没装错，那么我们把那个没装错的与n交换，即可得到一个全错位排列情况。

其他情况，我们不可能通过一次操作来把它变成一个长度为\(n\)的错排。

于是可得错位排列的递推式为\(f(n)=(n-1)(f(n-1)+f(n-2))\)。

错位排列数列的前几项为\(0,1,2,9,44,265\)。

圆排列

\(n\)个人全部来围成一圈，所有的排列数记为\(Q_n^n\)。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有 \(Q_n^n×n=A_n^n→Q_n^n=\frac{A_n^n}{n}=(n-1)!\) 部分圆排列公式 \(Q_n^r=\frac{A_n^r}{r}=\frac{n!}{r×(n-r)!}\)

求组合数的方法

递推处理

Note

适用于\(a,b \le 2000\)的情况

通过\((_b^a)=(_{b-1}^a)+(_{b-1}^{a-1})\)预处理

代码 

 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
#include<bits/stdc++.h>  
using namespace std;  
const int N=2005,mod=1e9+7;  
int c[N][N];  
void init(int n,int m)  
{  
    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-1]+c[i-1][j])%mod;  
        }  
    }  
}  
int main()  
{  
   init(2000,2000);  
   int n,a,b;  
   cin>>n;  
   for(int i=1;i<=n;i++)  
   {  
       cin>>a>>b;  
       cout<<c[a][b]<<endl;  
   }  
    return 0;  
}

逆元处理

Note

适用于\(a,b \le 1e5\)的情况

随取随用，用逆元,若询问多则选择预处理阶乘，\(C_a^b=\frac{fac[a]}{fac[b]*fac[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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
const int N=1e5+5,mod=1e9+7;  
int fac[N],infac[N];  
int qpow(int a,int n,int mod)  
{  
    int ans=1;  
    while(n)  
    {  
        if(n&1) ans=ans*a%mod;  
        a=a*a%mod;  
        n>>=1;  
    }  
    return ans;  
}  
void init()  
{  
    fac[0]=1;  
    infac[0]=1;  
    for(int i=1;i<N;i++)  
    {  
        fac[i]=fac[i-1]*i%mod;  
        infac[i]=infac[i-1]*qpow(i,mod-2,mod)%mod;  
    }  
}  
int C(int a,int b)  
{  
    return fac[a]*infac[b]%mod*infac[a-b]%mod;  
}  
signed main()  
{  
    int n;  
    cin>>n;  
    init();  
    //for(int i=1;i<=100;i++) cout<<fac[i]<<" "<<infac[i]<<endl;  
    for(int i=1;i<=n;i++)  
    {  
        int a,b;  
        cin>>a>>b;  
        cout<<C(a,b)<<endl;  
    }  
    return 0;  
}

Lucas定理

Note

适用于\(a≤1e18,b≤1e18,p≤1e5\)的取模情况

Lucas定理:

当\(p\)为质数时，有\(C_a^b=C_{a\ mod\ p}^{b\ mod\ p}\times C_{\frac{a}{p}}^{\frac{b}{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
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
int qpow(int a,int n,int mod)  
{  
    int ans=1;  
    while(n)  
    {  
        if(n&1) ans=ans*a%mod;  
        a=a*a%mod;  
        n>>=1;  
    }  
    return ans;  
}  
int C(int a,int b,int p)  
{  
    int res=1;  
    for(int i=1,j=a;i<=b;i++,j--)  
    {  
        res=res*j%p*qpow(i,p-2,p)%p;  
    }  
    return res;  
}  
int lucas(int a,int b,int p)  
{  
    if(a<b) return 0;  
    if(a<p&&b<p) return C(a,b,p);  
    else return lucas(a%p,b%p,p)*lucas(a/p,b/p,p)%p;  
}  
signed main()  
{  
    int n;  
    cin>>n;  
    for(int i=1;i<=n;i++)  
    {  
        int a,b,p;  
        cin>>a>>b>>p;  
        cout<<lucas(a,b,p)<<endl;  
    }  
    return 0;  
}

例1.Beautiful Numbers

题目入口

题解

对于每个\(n\)位数，只需要判断它的位数和是否good即可，暴力枚举a的数量，注意这里需要需处理阶乘

代码

 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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,n;
const int mod=1e9+7,N=1e6+6;;
int fac[N];
void init()
{
    fac[0]=1;
    for(int i=1;i<=1000000;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
}
bool check(int x,int a,int b)
{
    while(x)
    {
        if(x%10!=a&&x%10!=b) return false;
        x/=10;
    }
    return true;
}
int qpow(int a,int n,int mod)
{
    int res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int C(int a,int b,int mod)
{
    return fac[a]*qpow(fac[b],mod-2,mod)%mod*qpow(fac[a-b],mod-2,mod)%mod;
}
void solve()
{
    init();
    cin>>a>>b>>n;
    int res=0;
    for(int i=0;i<=n;i++)
    {
        int tmp=i*a+(n-i)*b;
        if(!check(tmp,a,b)) continue;
        res+=C(n,i,mod);
        res%=mod;
    }
    cout<<res<<endl;
}
signed main()
{
    solve();
    return 0;
}