A30308. 手套配对
填空题
困难
知识点
题目描述
手套配对
题目描述
小杨有n对不同的手套，每对手套由左右各一只组成。
小杨想知道从中取出m只手套，m只手套恰好包含k对手套的情况有多少种。
小杨认为两种取出的情况不同，当且仅当两种情况取出的手套中存在不同的手套（同一对手套的左右手也视为不同的手套）。
输入格式
第一行包含一个正整数 t，代表测试用例组数。
接下来是t组测试用例。对于每组测试用例，一共一行。
第一行包含三个正整数 ，代表手套数量，取出的手套数和目标对数。
输出格式
对于每组测试数据，输出一个整数 n,m,k ，代表可能的情况数量对10^9 +7取模的结果。
输入样例
2
5 6 2
5 1 5
输出样例
120
0
对于全部数据，保证有 1≤t≤100000, 1≤n≤1000,1≤m≤2*n, 1≤k≤n。
参考答案
#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";
}
}
上一题
下一题