题解：SP10377 MECGROUP - project groups

NaraFluorine · 2025-08-18 02:07:26 · 题解

关于本题

本题涉及到简单组合数的计算，建议评黄。

题目翻译

某大学计算机系教授向学生问了一个关于年终项目的结组问题。他要求每组至少包含 4 个男生和 1 个女生。

Rajesh 是一个有好奇心的人，他想知道对于一个组有多少种结组情况。但是他很忙，所以请你写一个程序帮帮他算出答案。

输入格式

第一行是一个整数 n，表示有多少个测试用例。

每个测试用例包含三个数字 B \, G \, t，分别代表男生有多少人，女生有多少人，一组要求有多少个人。

约束条件

对于所有测试数据，保证：

• ## 输出格式 对于每个测试用例，一行一个整数表示答案。 ## 样例1 输入 ``` 2 4 1 5 30 30 20 ``` ## 样例1 输出 ``` 1 4191318957352590 ``` # 题解 发现 $B,G$ 和 $n$ 都很小，考虑暴力。

假设当前 t 人中男生为 i，女生数量就是 t-i，对于这一种数量的贡献是 \binom{B}{i}\binom{t-i}{G}，直接累加。

对于组合数，本题没有设置模数限制，所以不能预处理阶乘，考虑使用杨辉三角。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
i64 yh[114][114];
void init(int num){
    for(int i=1;i<=num;++i){
        yh[i][1]=yh[i][i]=1;
        for(int j=2;j<i;++j){
            yh[i][j]=(yh[i-1][j]+yh[i-1][j-1]);
        }
    }
}
i64 C(int n,int m){
    return yh[n+1][m+1];
}
i64 n,m,tt,res;
//define NaraFluorine
int main(){
    init(100);
    int t=1;
    cin>>t;
    while(t--){
        cin>>n>>m>>tt;
        res=0;
        for(i64 i=4;i<=n;++i){
            for(i64 j=1;j<=m;++j){
                if((i+j)==tt){
                    res+=C(n,i)*C(m,j);
                }
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}