[GESP202409八级] 手套配对

• 难度：普及/提高-

• 标签：组合数

观察数据发现 $T == 10 ^ 5$ 且 $N, M$ 都在 $1000$ 左右。因此不好尝试枚举什么信息计算答案。

尝试组合数求解：因为题目要求恰好 $K$ 对手套，因此表明这 $K$ 对手套的左右手必须都选，此部分答案贡献为 $$\binom{N}{K}$$ 。考虑剩下没选的 $N - K$ 对手套当中，对于每一对手套，我们要不两只都不选，要么只能选其中一只，因此该部分答案贡献为 $$\binom{N - K}{M - K * 2} * 2^{M - K * 2}$$。两部分答案贡献乘起来即可。

/*
注意：数据特判，模值为1e9+7时，及时是ll也要需要注意溢出情况 
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int P=1e9+7;
int t,n,m,k;
int c[2505][2505],e[2505];
int main(){
	for(int i=0;i<=2000;i++){
		for(int j=0;j<=i;j++){
			if(j==0||i==j){
				c[i][j]=1;
			}
			else{
				c[i][j]=c[i-1][j]+c[i-1][j-1];
				c[i][j]%=P;
			}
		}
	}
	e[0]=1;
	for(int i=1;i<=2000;i++){
		e[i]=e[i-1]*2;
		e[i]%=P;
	}
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		if(m<2*k||m-2*k>n-k){
			cout<<"0\n";
		}
		else{
			cout<<1ll*c[n][k]*c[n-k][m-2*k]%P*e[m-2*k]%P<<endl;
		}
	}
	return 0;
}