G8007 [GESP202409 八级] 手套配对 题解

知识点：组合计数、动态规划预处理、取模。

解题思路

先选k种取完整左右手的颜色，再从剩余n-k种选m-2k种各取一只，每种单只可选左右两种，方案为C(n,k)C(n-k,m-2k)2^(m-2k)。

为什么正确

“完整配对颜色、单只颜色、每个单只的左右类型”唯一确定选取方案，三步独立相乘且不重复。

易错点

m-2k必须非负且不超过n-k；不要把一对左右手交换顺序当成新方案，模10^9+7。

复杂度

预处理O(U²)，每组O(1)，空间O(U²)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const long long M=1000000007;
    vector<vector<long long>>C(1001,vector<long long>(1001));
    for(int n=0;n<=1000;n++) {
        C[n][0]=C[n][n]=1;
        for(int k=1;k<n;k++)C[n][k]=(C[n-1][k-1]+C[n-1][k])%M;
    }
    vector<long long>pw(2001,1);
    for(int i=1;i<=2000;i++)pw[i]=pw[i-1]*2%M;
    int t;
    cin>>t;
    while(t--) {
        int n,m,k;
        cin>>n>>m>>k;
        int single=m-2*k;
        if(single<0||single>n-k)cout<<0;
        else cout<<C[n][k]*C[n-k][single]%M*pw[single]%M;
        cout<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。