GESP认证C++编程真题解析 | P11250 [GESP202409 八级] 手套配对

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11250 [GESP202409 八级] 手套配对 - 洛谷

【题目描述】

小杨有n nn对不同的手套，每对手套由左右各一只组成。

小杨想知道从中取出m mm只手套，m mm只手套恰好包含k kk对手套的情况有多少种。

小杨认为两种取出的情况不同，当且仅当两种情况取出的手套中存在不同的手套（同一对手套的左右手也视为不同的手套）。

【输入】

本题单个测试点内有多组测试数据。

第一行包含一个正整数t tt，代表测试用例组数。

接下来是t tt组测试用例。对于每组测试用例，一共一行。

第一行包含三个正整数n , m , k n,m,kn,m,k，代表手套数量，取出的手套数和目标对数。

【输出】

对于每组测试数据，输出一个整数，代表可能的情况数量对10 9 + 7 10^9+7109+7取模的结果。

【输入样例】

2 5 6 2 5 1 5

【输出样例】

120 0

【算法标签】

《洛谷 P11250 手套配对》 #组合数学# #排列组合# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=1005,mod=1e9+7;intt;// 测试用例数量intn,m,k,ans;// n: 总数, m: 选择数量, k: 特定对数, ans: 答案intc[N][N];// 组合数C(n, m)数组intd[N];// 2的幂次数组// 初始化组合数C(n, m) = C(n-1, m-1) + C(n-1, m)voidinit(){c[0][0]=1;// C(0,0) = 1for(inti=1;i<=1000;i++){for(intj=0;j<=i;j++){if(j==0)// C(i,0) = 1{c[i][j]=1;}else{// 组合数递推公式c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}}}// 初始化2的幂次数组voidinit2(){d[0]=1;// 2^0 = 1for(inti=1;i<=1000;i++){d[i]=d[i-1]*2%mod;// 2^i = 2^(i-1) * 2}}signedmain()// 由于定义了#define int long long，需要使用signed main{cin>>t;// 预处理组合数和2的幂init();init2();while(t--){cin>>n>>m>>k;// 条件检查：必须满足的基本限制// 1. m >= 2k: 至少需要2k个元素来形成k对// 2. m - 2k <= n - k: 剩余选择的元素不能超过可用的元素if(m<2*k||m-2*k>n-k){cout<<0<<endl;}else{// 计算答案公式：C(n,k) * C(n-k, m-2k) * 2^(m-2k)intans=((c[n][k]*c[n-k][m-2*k])%mod*d[m-2*k])%mod;cout<<ans<<endl;}}return0;}

【运行结果】

2 5 6 2 120 5 1 5 0