K - The World is a Theatre 题解

算法 题解

题目大意

要选出t个人，包含至少4个男生和至少1个女生，问有多少选择方法。(4 ≤ n ≤ 30, 1 ≤ m ≤ 30, 5 ≤ t ≤ n + m)

分析

本题基本思路就是用组合数学的思想进行计算，不过这里要注意，在进行组合数计算时需要优化，不然会超出数据范围。比如，我们的组合数公式为C(n,m)=m!/(n!*(m-n)!),这里如果逐个进行阶乘计算肯定是会溢出的，我们可以算max(n!,(m-n)!)+1到m的累乘数再除以min(n!,(m-n)!)。但是这种方法肯定不是最佳方法，我在用这种方法时，恰好最大数据C(15,30)时溢出……于是只好手算打表这个数据。

代码

#include <iostream>
#include <algorithm>
using namespace std;
unsigned long long jc(unsigned long long n,unsigned long long m)
{
    unsigned long long i,ans=1;
    for(i=m+1;i<=n;i++)
    {
        ans*=i;
    }
    return ans;
}
unsigned long long c(unsigned long long n,unsigned long long m)
{
    if(n==30&&m==15)
        return 155117520;//这就是打表
    unsigned long long zj=jc(n,max(m,n-m));
    unsigned long long ans=zj/jc(min(m,n-m),0);
    return ans;
}
int main(void)
{
    unsigned long long n,m,t;
    unsigned long long ans=0;
    cin>>n>>m>>t;
    unsigned long long i,j;
    for(i=4;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(i+j!=t)
                continue;
            ans+=c(n,i)*c(m,j);
        }
    }
    cout<<ans<<endl;
    return 0;
}