新生晚会 HDU-2519 【计算排列组合】

题意： 一场舞会，需要从n个人里挑出m个人上台表演，问共有多少种情况。

思路：即求c(m,n) 。 在计算过程中有点技巧，注释在代码里

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[50];
int main(void)
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n >>m;
        if(n<m ) cout << "0"<<endl;
        else
        {
            a[0]=1; // 解决了m=0的问题，同时为下面a[1]计算做铺垫
            for(int i=1;i<=m;i++)
                a[i]=a[i-1]*(n-i+1)/i;//先乘再除
            cout << a[m]<< endl;
        }
    }
}
2018.10.13
用逆元求组合数

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){//comb(n, m)就是C(n, m)
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}
int main()
{
    init();
    int t,n,m;
    cin >>t ;
    while(t--){
        cin >>n >>m;
        ll ans=comb(n,m);
        cout << ans << endl;
    }

}