简答题
偏难
#20834
手套配对 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有 n 对不同的手套,每对手套由左右各一只组成。 小杨想知道从中取出 m 只手套,m…
手套配对
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 对不同的手套,每对手套由左右各一只组成。
小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。
小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,一共一行。
第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。
输出格式
对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。
输入样例
输出样例

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
const int p = 1e9+7;
#define ll long long
ll c[N][N];
ll pw[N];
int n,m,k;
void init(){
pw[0]=1;
for(int i=0;i<N;i++){
if(i)pw[i]=pw[i-1]*2%p;
for(int j=0;j<=i;j++){
if(j==0)c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
}
}
int main(){
init();
int t;
cin>>t;
while(t--){
cin>>n>>m>>k;
if(m<2*k||m-2*k>n-k){
cout<<"0\n";
continue;
}
ll ans=c[n][k]*c[n-k][m-2*k]%p;
ans=ans*pw[m-2*k]%p;
cout<<ans<<"\n";
}
}</pre>
这道题暂未补解析。