关于本题

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

题目翻译

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

4

个男生和

1

个女生。

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

输入格式

第一行是一个整数

n

，表示有多少个测试用例。

每个测试用例包含三个数字

B \, G \, t

，分别代表男生有多少人，女生有多少人，一组要求有多少个人。

约束条件

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

$1≤n≤20$ ；
$4≤B≤30$ ；
$1≤G≤30$ ；
$5≤t≤B+G$ 。

输出格式

对于每个测试用例，一行一个整数表示答案。

样例1 输入

CPP

2
4 1 5
30 30 20

样例1 输出

CPP

1
4191318957352590

题解

发现

B,G

和

n

都很小，考虑暴力。

假设当前

t

人中男生为

i

，女生数量就是

t-i

，对于这一种数量的贡献是

\binom{B}{i}\binom{t-i}{G}

，直接累加。

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

代码如下：

CPP

#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;
}

题解：SP10377 MECGROUP - project groups

文章操作