手套配对(Glove Pairing) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<vector<int>> C(1005, vector<int>(1005, 0));
    vector<int> pw2(2005, 1);
    for (int i = 1; i <= 2000; ++i) pw2[i] = pw2[i - 1] * 2 % MOD;
    for (int i = 0; i <= 1000; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        int single = m - 2 * k;
        if (k < 0 || k > n || single < 0 || single > n - k) {
            cout << 0 << "\n";
            continue;
        }
        long long ans = 1LL * C[n][k] * C[n - k][single] % MOD * pw2[single] % MOD;
        cout << ans << "\n";
    }
    return 0;
}