思路讲解
一道非常经典的排列组合的题。
首先,我们要先从 n n n 对手套中取走 k k k 对,容易想到方案数为 C n k C_{n}^{k} Cnk。
接下来,因为我们要恰好取走 k k k 对手套,所以剩下取走的 m − 2 × k m-2\times k m−2×k 只手套中不能出现有两个属于同一对的情况,所以我们只能从剩下的 n − k n-k n−k 对手套中选出 m m m 对,各取走一只左手套或者右手套,方案数为 2 m − 2 × k × C n − k m − 2 × k 2^{m-2\times k} \times C_{n-k}^{m-2\times k} 2m−2×k×Cn−km−2×k。
最终,答案为 C n k × 2 m − 2 × k × C n − k m − 2 × k C_{n}^{k} \times 2^{m-2\times k} \times C_{n-k}^{m-2\times k} Cnk×2m−2×k×Cn−km−2×k。
我们只需通过杨辉三角预处理组合数,再预处理 2 2 2 的整数幂(当然也可以用快速幂),最后直接输出答案即可。
需要注意的是,预处理和统计答案时要及时取模,并且输出时要开 long long
,否则可能会超过变量的上限。还有当
m
−
2
×
k
<
0
m-2\times k<0
m−2×k<0 或
m
−
2
×
k
>
n
−
k
m-2\times k>n-k
m−2×k>n−k 时要直接输出
0
0
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;
}
标签:预处理,时要,GESP202409,int,题解,times,手套,P11250,mod
From: https://blog.csdn.net/andycode_/article/details/143677763