题解：P11250 [GESP202409 八级] 手套配对

题目

小杨有 对不同的手套，每对手套由左右各一只组成。

小杨想知道从中取出 只手套，恰好包含 对手套的情况有多少种。

小杨认为两种取出的情况不同，当且仅当两种情况取出的手套中存在不同的手套（同一对手套的左右手也视为不同的手套）。

**本题目多测。**对全部的测试数据，保证 ，，，。

题解

本题目比较简单：

• 对中取出 对，；
• 选 对，每对有左/右两种可能，；

可预处理 ，便于多测计算，代码中前者选用杨辉三角递推法：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 1005;
const LL mod = 1e9+7;

int T;
int n, m, k;
LL C[MAXN][MAXN];
LL Pow[MAXN];

inline void C_init() {
    for (int i = 0; i < MAXN; ++i)
        for (int j = 0; j <= i; ++j) {
            if (j == 0)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    return;
}
inline void Pow_init() {
    Pow[0] = 1;
    for (int i = 1; i < MAXN; ++i)
        Pow[i] = (Pow[i - 1] << 1) % mod;
    return;
}

int main() {
    C_init();
    Pow_init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        if (m < (k << 1) || (n - k) < (m - (k << 1))) {
            cout << 0 << '\n';
            continue;
        }
        /*
        特判边界：
        1. 根据数学判断，C 中下标一定不能比上标更小；
        2. 根据下标判断，数组下标一定不能小于零；
        3. 根据现实意义判断，一定要有足够多的手套；
        */
        LL C_pair = C[n][k];
        LL C_single = (C[n - k][m - (k << 1)] * Pow[m - (k << 1)]) % mod;
        cout << (C_pair * C_single) % mod << '\n';
    }
    return 0;
}