Talk is Cheap, Show Me the Code!

0%

组合计数

Posted on In

求组合数，C(n, m)% P。

输入描述:

两个整数n和m

输出描述:

C(n,m) 表示的结果

示例1
输入

6 3

输出

20

zuheshu1.cppview raw
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
#include <iostream>
#include <vector>
using namespace std;

const int N = 1000010, P = 1e9+7;
int cnt[N+10];
vector<int> son[N+10];
int n, m;

void prime(){
    for(int i=2;i<=N;i++){
        if(son[i].size()==0)
            for(int j=i;j<=n;j+=i) {
                son[j].push_back(i); //该数是质数， 包含该质数因子本身
            }
    }
}

void solve(int n, int k){
    for(int i=2;i<=n;i++)
        for(int j=0;j<son[i].size();j++){
            int x = son[i][j], c = 0, p=i;
            while(p%x==0){
                p/=x, c++;
            }
            cnt[x] += c*k;
        }
}

long long fast(int a, int b){
    long long res = 1;
    while(b){
        if(b&1) res = res * a % P;
        a = a * a % P;
        b>>=1;
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    prime();
    solve(n, 1);
    solve(n-m, -1);
    solve(m, -1);

    long long res = 1;
    for(int i=2;i<=n;i++)
        if(cnt[i]>0)
            res = res * fast(i, cnt[i]) % P;
    printf("%lld\n", res);
    return 0;
}
zuheshu2.cppview raw
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
#include <iostream>
using namespace std;

const int N = 1000010, P = 1e9+7;

int n, m;

int pcnt, pr[N+10];
int cnt[N+10];
int mark[N+10];

void prime(){
    for(int i=2;i<=N;i++)
        if(!mark[i]) {
            pr[++pcnt] = i;
            for (int j = i + i; j <= n; j += i)
                mark[j] = 1;
        }
}

//阶乘质因子分解
void solve(int n, int k){
    for(int i=1; i<=pcnt && pr[i]<=n;i++){  //starts from 1
        int x = pr[i];
        // x在n!中指数
        long long t = x;
        while(t<=n){
            cnt[x] += n/t * k;
            t*=x;
        }
    }
}

long long fast(int n, int x){
    long long res = 1;
    while(x){
        if(x&1) res = res * n % P;
        n = n * n % P;
        x >>= 1;
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    prime();
    solve(n, 1);
    solve(n-m, -1);
    solve(m, -1);
    long long res = 1;
    for(int i=2;i<=n;i++)
        if(cnt[i])
            res = res * fast(i, cnt[i]) % P;
    printf("%lld\n", res);
    return 0;
}
zuheshu3.cppview raw
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;
#define ll long long
ll T,f[1000009],n,m;
const int p=1e9+7;
ll fast(ll x,int b){
    ll res=1;
    while(b>0){
        if(b&1)res=res*x%p,res%=p;
        x=x*x%p,x%=p;
        b/=2;
    }
    return res;
}
int main(){
    f[0]=1;
    for(int i=1;i<=1000000;i++)f[i]=(f[i-1]%p*i)%p;
    char in[20]={"data0.in"};
    char out[20]={"data0.out"};
    for(int cas=1;cas<=10;cas++){
        freopen(in,"r",stdin);in[4]++;
        freopen(out,"w",stdout);out[4]++;

        scanf("%d %d",&n,&m);
        //cerr<<n<<" "<<m<<endl;
        // 除法转为逆元+费马小定理
        printf("%lld\n",f[n]%p*fast(f[m],p-2)%p*fast(f[n-m],p-2)%p);
    }
    return 0;
}