Hexo
0%

8-排列组合数

发表于

排列组合

排列就是指从给定个数的元素中取出指定个数的元素进行排序。
组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

(0)预定义

1
2
3
typedef long long ll;
ll mod=1e9+7;
const int MAXN=1001;

(1)排列

Anm=n(n−1)···(n−m+1)=n!(n−m)!

求Anm=n(n−1)···(n−m+1)

1
2
3
4
5
6
7
8
9
ll get_perm(ll n,ll m) {
    ll ans=1;
    for(ll i=n;i>n-m;--i)
    {
        ans*=i;
        ans%=mod;
    }
    return ans;
}

(2)组合

Cnm=Anmm!=n!m!(n−m)!=Cnn−m

求Cnm=n(n−1)···(m+1)(n−m)!

1
2
3
4
5
6
7
8
ll get_comb(ll n,ll m) {
    ll ans=1;
    for(ll i=n;i>m;--i)
        ans*=i;
    for(ll i=n-m;i>0;--i)
        ans/=i;
    return ans%mod;
}

(3)求一定范围内排列数

性质1：可理解为“某特定位置”先安排，再安排其余位置。

Anm=nAn−1m−1

性质2：分为含特定元素的排列和不含特定元素的排列。

Anm=mAn−1m−1+An−1m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//$A_{n}^{m}$即perm[n][m]
//上面是m，下面是n
//perm[n][m]=comb[n][m]*m!
ll perm[MAXN][MAXN];
void build_perm(int limit)
{
    //memset(perm,0,sizeof(perm));
    for (int n=0;n<=limit;++n)
        for (int m=0;m<=n;++m)
        {
            if (m==0)
                perm[n][m]=1;
            else
                perm[n][m]=n*(perm[n-1][m-1])%mod;
        }
}

(4)求一定范围内组合数

基本性质1：

Cn0=Cnn=1

基本性质2：分为含特定元素的组合和不含特定元素的组合

Cnm=Cn−1m+Cn−1m−1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//$C_{n}^{m}$即comb[n][m]
//上面是m，下面是n
ll comb[MAXN][MAXN];
void build_comb(int limit)
{
    //memset(comb,0,sizeof(comb));
    for (int n=1;n<=limit;++n)
        for (int m=0;m<=n;++m)
        {
            if (m==n || m==0)
                comb[n][m]=1;
            else
                comb[n][m]=(comb[n-1][m]%mod+comb[n-1][m-1]%mod)%mod;
        }
}

(5)模板

perm_comb.h

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
#ifndef PERM_COMB
#define PERM_COMB

typedef long long ll;
ll mod=1e9+7;
const int MAXN=1001;

//$C_{n}^{m}$即comb[n][m]
//上面是m，下面是n
ll comb[MAXN][MAXN];
void build_comb(int limit)
{
    //memset(comb,0,sizeof(comb));
    for (int n=1;n<=limit;++n)
        for (int m=0;m<=n;++m)
        {
            if (m==n || m==0)
                comb[n][m]=1;
            else
                comb[n][m]=(comb[n-1][m]%mod+comb[n-1][m-1]%mod)%mod;
        }
}

//$C_{n}^{m}$即comb[n][m]
//上面是m，下面是n
ll get_comb(ll n,ll m) {
    ll ans=1;
    for(ll i=n;i>m;--i)
        ans*=i;
    for(ll i=n-m;i>0;--i)
        ans/=i;
    return ans%mod;
}

//$A_{n}^{m}$即perm[n][m]
//上面是m，下面是n
//perm[n][m]=comb[n][m]*m!
ll perm[MAXN][MAXN];
void build_perm(int limit)
{
    //memset(perm,0,sizeof(perm));
    for (int n=0;n<=limit;++n)
        for (int m=0;m<=n;++m)
        {
            if (m==0)
                perm[n][m]=1;
            else
                perm[n][m]=n*(perm[n-1][m-1])%mod;
        }
}

//$A_{n}^{m}$即perm[n][m]
//上面是m，下面是n
ll get_perm(ll n,ll m) {
    ll ans=1;
    for(ll i=n;i>n-m;--i)
    {
        ans*=i;
        ans%=mod;
    }
    return ans;
}

#endif