2024年9月GESP真题及题解(C++八级): 手套配对

2024年9月GESP真题及题解(C++八级): 手套配对

题目描述

小杨有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取模的结果。

输入输出样例 1

输入 1

2 5 6 2 5 1 5

输出 1

120 0

说明/提示

对全部的测试数据，保证1 ≤ t ≤ 10 5 , 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 2 × n , 1 ≤ k ≤ n 1 \leq t \leq 10^5,1 \leq n \leq 1000,1 \leq m \leq 2 \times n,1 \leq k \leq n1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。

思路分析

这是一个组合计数问题。我们有 n 对不同的手套，每对手套有左、右手各一只。需要从这 2n 只手套中取出 m 只手套，使得取出的手套恰好包含 k 对完整的手套（即 k 对手套的左右手都在取出的集合中）。

关键点：

• 每对手套的左右手是不同的（即左手和右手是不同的手套）
• 恰好包含 k 对完整的手套
• 剩下的 (m-2k) 只手套必须是单只的，不能形成新的完整对
• 单只的手套不能来自已经配对的 k 对（否则那一对就不完整了）

推导过程：

1. 选择完整的 k 对：从 n 对中选择 k 对，方案数：C(n, k)

2. 剩下的 (m-2k) 只单只手套：

   • 这些单只手套必须来自剩下的 (n-k) 对中
   • 从 (n-k) 对中，每对最多取 1 只（否则会形成新的完整对）
   • 从 (n-k) 对中选择 (m-2k) 对，方案数：C(n-k, m-2k)
   • 对于选择的每一对，可以取左手或右手，方案数：2m − 2 k ^{m-2k}m−2k

3. 总方案数：C(n, k) × C(n-k, m-2k) × 2m − 2 k ^{m-2k}m−2k

4. 边界条件：

   • 当 m < 2k 时：不可能有 k 对完整的手套
   • 当 m-2k > n-k 时：不可能从 (n-k) 对中取出那么多单只手套（因为每对最多取 1 只）
   • 当 k > n 时：不可能有那么多对完整的手套

算法设计：

1. 预处理组合数 C[ n ] [ k ] [n][k][n][k]和 2 的幂次
2. 对于每个查询，判断边界条件
3. 计算组合数公式

时间复杂度：

• 预处理组合数：O(N²)，N=1000
• 每个查询：O(1)
• 总复杂度：O(N² + T)，可以接受

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMOD=1e9+7;constintN=1010;// n的最大值constintM=2010;// m的最大值// 组合数表ll C[N][N];// 2的幂次表ll pow2[M];// 预处理组合数和2的幂voidinit(){// 组合数预处理for(inti=0;i<N;i++){C[i][0]=C[i][i]=1;for(intj=1;j<i;j++){C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}}// 2的幂预处理pow2[0]=1;for(inti=1;i<M;i++){pow2[i]=(pow2[i-1]*2)%MOD;}}intmain(){init();intt;cin>>t;while(t--){intn,m,k;cin>>n>>m>>k;// 边界条件检查if(m<2*k){cout<<0<<endl;continue;}intsingle=m-2*k;// 单只手套数量// 单只手套不能超过剩余的对数if(single>n-k){cout<<0<<endl;continue;}// 计算方案数ll ans=C[n][k];// 选择k对完整手套ans=ans*C[n-k][single]%MOD;// 选择哪些对取单只ans=ans*pow2[single]%MOD;// 每对可以选择左手或右手cout<<ans<<endl;}return0;}

功能分析

变量说明：

• C[N][N]：组合数表，C[i][j]表示从 i 个中选 j 个的组合数
• pow2[M]：2 的幂次表，pow2[i]表示 2^i
• n：手套对数
• m：取出的手套总数
• k：目标完整对数
• single = m - 2*k：单只手套的数量

函数说明：

• init()：预处理组合数表和 2 的幂次表
  • 组合数使用递推公式：C(n,k) = C(n-1,k) + C(n-1,k-1)
  • 2 的幂使用递推：2^i = 2^(i-1) * 2

边界条件检查：

1. if (m < 2 * k)：如果取出的手套总数少于 2k，不可能有 k 对完整的手套
2. if (single > n - k)：如果单只手套数量大于剩余的对数，无法满足每对最多取 1 只的条件

公式计算：

1. C[n][k]：从 n 对中选择 k 对完整手套
2. C[n-k][single]：从剩余的 (n-k) 对中选择 single 对来取单只手套
3. pow2[single]：对于每个选择的单只手套，可以取左手或右手

示例测试：

输入：

2 5 6 2 5 1 5

计算过程：

1. n=5, m=6, k=2

   • single = 6-4 = 2
   • 检查：m=6≥2k=4，single=2≤n-k=3
   • 计算：C[ 5 ] [ 2 ] [5][2][5][2]= 10, C[ 3 ] [ 2 ] [3][2][3][2]= 3, pow2[2] = 4
   • 结果：10×3×4 = 120

2. n=5, m=1, k=5

   • single = 1-10 = -9
   • 检查：m=1<2k=10 → 输出 0

复杂度分析：

• 预处理：O(N²) = 1000×1000 = 1e6 次运算
• 每个查询：O(1) 直接查表计算
• 总查询：最多10 5 10^5105次，总复杂度可行

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}