自动搬运

查看原文

来自洛谷，原作者为

	andycode Aways continue,never break|服役OIer|等级分要冲上去呀！|代词使用他

搬运于2025-08-24 23:05:43，当前版本为作者最后更新于2024-11-08 15:30:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路讲解

一道非常经典的排列组合的题。

首先，我们要先从 $n$ 对手套中取走 $k$ 对，容易想到方案数为 $C_{n}^{k}$。

接下来，因为我们要恰好取走 $k$ 对手套，所以剩下取走的 $m-2\times k$ 只手套中不能出现有两个属于同一对的情况，所以我们只能从剩下的 $n-k$ 对手套中选出 $m$ 对，各取走一只左手套或者右手套，方案数为 $2^{m-2\times k} \times C_{n-k}^{m-2\times k}$。

最终，答案为 $C_{n}^{k} \times 2^{m-2\times k} \times C_{n-k}^{m-2\times k}$。

我们只需通过杨辉三角预处理组合数，再预处理 $2$ 的整数幂，最后直接输出答案即可。

需要注意的是，预处理和统计答案时要及时取模，并且输出时要开 long long，否则可能会超过变量的上限。还有当 $m-2\times k<0$ 或 $m-2\times k>n-k$ 时要直接输出 $0$。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,m,k;
int C[1003][1003],mi[2003];
int main(){
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=i;j++)
            C[i][j]=(j==0 || j==i?1:C[i-1][j]+C[i-1][j-1]),C[i][j]%=mod;
    mi[0]=1;
    for(int i=1;i<=2000;i++)
        mi[i]=mi[i-1]*2%mod;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        if(m-2*k<0 || m-2*k>n-k)
            printf("0\n");
        else
            printf("%lld\n",(1LL*C[n][k]*mi[m-2*k]%mod)*C[n-k][m-2*k]%mod);
    }
    return 0;
}