算法

从 $m$ 只手套中恰好选出 $k$ 对手套，可以考虑将每对手套看成一个整体，那么我们可以从这 $n$ 对手套中任选 $k$ 对手套，有 ${}_n\mathrm{C}_k$ 种方案，还需要选出剩下不能配对的 $m-2k$ 只手套，意味着需要在剩下的每对手套中任选一只，所以方案数为 ${}_{n-k}\mathrm{C}_{m-2k} \cdot 2^{m-2k}$。由于这里是分步骤，所以将两种方案数乘起来即可。

C++ 代码

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int k2 = k*2;

    if (m < k2 or m-k2 > n-k) {
        puts("0");
        return;
    }

    mint ans = comb(n, k) * comb(n-k, m-k2);
    ans *= mint(2).pow(m-k2);
    cout << ans << '\n';
}