简答题 偏难
#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 取模的结果。

输入样例

2
5 6 2
5 1 5

输出样例

120
0

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; 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&lt;N;i++){ if(i)pw[i]=pw[i-1]*2%p; for(int j=0;j&lt;=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&gt;&gt;t; while(t--){ cin&gt;&gt;n&gt;&gt;m&gt;&gt;k; if(m&lt;2*k||m-2*k&gt;n-k){ cout&lt;&lt;"0\n"; continue; } ll ans=c[n][k]*c[n-k][m-2*k]%p; ans=ans*pw[m-2*k]%p; cout&lt;&lt;ans&lt;&lt;"\n"; } }</pre>
这道题暂未补解析。