手套配对题解

思路推导

先从 $n$ 对手套中选出恰好完整出现的 $k$ 对。剩余需要选 $m-2k$ 只手套，而且它们必须来自不同的手套对，否则完整手套对数量会增加。

做法

先选择 $k$ 对完整手套，共有 $\binom nk$ 种。再从剩余 $n-k$ 对中选择 $m-2k$ 对，每对选择左或右其中一只，因此方案数为 $\binom nk\binom{n-k}{m-2k}2^{m-2k}$。

若 $m-2k<0$ 或 $m-2k>n-k$，答案为零。预处理阶乘、逆阶乘和二的幂后即可常数时间回答每组数据。

正确性证明

任意合法方案都能唯一分成 $k$ 对完整手套与 $m-2k$ 只来自互不相同手套对的单只手套。公式的三部分分别选择完整手套对、只出现一只的手套对以及每对中具体选择的左右手套。该分解与构造互为逆过程，因此公式不重不漏。

复杂度分析

预处理时间和空间复杂度均为 $O(1000)$；每组数据的时间复杂度为 $O(1)$。