题解 | 人员分组问题

问题描述：

某公司计划成立一个创新小组，要求 恰好 由 5∼7 人组成。公司共收到 n 份应聘简历，需要统计所有可能的小组组合数量。

结果可能非常大，请输出方案数对 1000000007 取模后的值。

输入描述：

在一行上输入一个整数 n(1≦n≦1000000)表示应聘者数量。

输出描述：

输出一个整数，表示所有满足条件的小组组合数量模 10000000007 的结果。

问题分析：

实际上就是数学中的组合问题，分别求出C(n,5)、C(n,6)、C(n,7)，再相加就行。

问题就是虽然单个数字在int取值范围内，但n可能很大，那么好几个大的数相乘就可能变很大，那么就不能直接套用公式。

那么如果每次相乘都取模呢？显然不行，因为可能取完模后的值变小，但是计算组合数还得除以一个k！，结果就有可能出错。

所以就是考虑怎样将分子中的k！通过分母进行约分，然后再计算分子中的数，每次相乘都取模。结果就不会出错了

#include <iostream>
#include <array>
using namespace std;

#define M_num 1000000007;

long long M_Pow(int n,int k){
    long long num=1;
    int j=k;
    int a[k];//存储k个值
    for(int i=0;i<k;++i) a[i]=n-i;
    while(k>1){
        for(int i=0;i<j;++i){
            if(a[i]%k==0) {
                a[i]/=k;
                break;
            }
        }//将求组合数的公式中分母部分全部由分子部分消掉
        --k;
    }
    for(int i=0;i<j;++i) num=num*a[i]%M_num;
    return num;
}

int main() {
    int n;
    long long int ans=0;
    cin>>n;
    int d[8]={0,0,0,0,0,1,7,29};
     if(n<8){
        cout<<d[n]<<endl;
        return 0;
    }
    ans+=M_Pow(n,5);
    ans+=M_Pow(n,6);
    ans+=M_Pow(n,7);
    ans%=M_num;
    cout<<ans<<endl;
    return 0;    
}
// 64 位输出请用 printf("%lld")