GESP 题解库 / 8 级题解 / [GESP202409 八级] 手套配对 · 第 14 / 24 题
GESP202409 八级 · P11250 · 中等

手套配对计数

先选定"被取全的 k 对",剩下的每对至多取一只,再乘上左右手的 2 种选法。

🧤
n ≤ 1000
手套对数(共 2n 只)
🎯
模 10⁹ + 7
质数,可求逆元
⚡
O(2000 + t log m)
预处理 + 快速幂
🧮
C(n, k) × C(n − k, m − 2k) × 2^(m − 2k)
核心公式
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

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

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

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

输入格式

本题单个测试点内有多组测试数据。第一行一个正整数 t,代表测试用例组数。

接下来 t 组测试用例,每组一行,包含三个正整数 n, m, k,代表手套对数、取出的手套数和目标对数。

输出格式

对于每组测试数据,输出一个整数,代表可能的情况数量对 10⁹ + 7 取模的结果。

样例

样例输入输出
#12
5 6 2
5 1 5
120
0
💡
人话翻译:一共有 2n 只互不相同的手套(每对分左右手,全都不一样)。
取 m 只出来,要求其中恰好有 k 对是"整对都被取到"(这一对的左右两只都在取出的集合里)。
计数口径:只看"取出的手套集合",顺序无关;左右手算不同手套。
思路(先选对、再选只):① 先决定哪 k 对整对取全:C(n, k) 种,这已经用掉 2k 只;② 剩下的 m − 2k 只只能从其余 n − k 对里出,而且每一对至多只能取一只(取两只就变成第 k + 1 对完整了);
于是先从 n − k 对里挑出 m − 2k 对:C(n − k, m − 2k),每对被挑中的对子里"取左手还是右手"还有 2 种,合起来乘 2^(m − 2k)。
三步相乘就是答案。

🔍 关键词提取

组合计数乘法原理先选对再选只乘 2 的幂阶乘 + 逆元预处理

已知条件

项目说明
输入第一行 t;随后 t 行每行 n、m、k
输出每组一行,答案对 10⁹ + 7 取模
数据范围1 ≤ t ≤ 10⁵,1 ≤ n ≤ 1000,1 ≤ m ≤ 2n,1 ≤ k ≤ n
模数10⁹ + 7,是质数 → 可以用费马小定理求逆元
计数口径集合(与顺序无关);同一对的左右手视为不同手套
部分分30% 是 k = 1;30% 是 n ≤ 5 且 m ≤ 10;40% 全范围

需要解决的问题

02
思维导图
整理解题思路的全貌
🧮 先选取全的 k 对,再在剩余对里"单只"选
🧾 计数口径
共 2n 只互不相同的手套
左右手算不同手套
取法只看集合,与顺序无关
"完整对"= 该对两只都被取到
🅰️ 第一步:选完整对
从 n 对里挑 k 对整对取全
方案数 C(n, k)
这 k 对已经用掉 2k 只
剩下的完整对必须为 0
🅱️ 第二步:在剩余对里取单只
还剩 n − k 对可用
还要取 r = m − 2k 只
每对至多 1 只 → 先挑 r 对:C(n − k, r)
每对 2 种方向 → 乘 2^r
⚠️ 易错点
忘记乘 2^r(只算"选哪几对")
不判 r < 0 与 r > n − k
n − k < 0 时数组越界
用 int 存阶乘乘积(要先取模)
03
样例手算推导
样例 1 逐项核对 + 两个"必为 0"的边界

🧮 样例 1:n = 5、m = 6、k = 2 为什么是 120

把 5 对手套编号为 1…5,每对记为 i左 / i右,共 10 只。要取 6 只,恰好 2 对完整。

1
第一步:选定哪 2 对"整对取全"

从 5 对里挑 2 对:C(5, 2) = 10

这 2 对的左右两只都要拿,共 4 只

例如选定 {1, 3},则 1左、1右、3左、3右 都进集合

第一步 10 种

2
第二步:剩下 3 对里再挑"取单只"的对

总共要取 6 只,已经用掉 4 只 → 还差 r = 6 − 4 = 2 只

剩余可用对是 3 对,每对最多取 1 只

先挑出"要贡献一只"的 2 对:C(3, 2) = 3

例如剩余对是 {2, 4, 5},挑 {2, 5}

第二步 3 种

3
第三步:每对选左手还是右手

被挑中的 2 对,每对 2 种选择(左 / 右)

2 × 2 = 2² = 4

例如 2左 & 5右、2右 & 5左、2左 & 5左、2右 & 5右

第三步 4 种

4
三步相乘

C(5, 2) × C(3, 2) × 2²

= 10 × 3 × 4 = 120

✅ 120

环节公式本题取值含义
选完整对C(n, k)C(5, 2) = 10哪 2 对整对取全
选单只对C(n − k, m − 2k)C(3, 2) = 3剩下 3 对里挑 2 对各取一只
选方向2^(m − 2k)2² = 4每对取左或取右
合计C(n,k) · C(n−k, m−2k) · 2^(m−2k)10 × 3 × 4 = 120对 10⁹ + 7 取模后仍是 120
🔑
为什么"先选对"不会重复计数?每取出的 m 只手套集合,它的"完整对集合"是唯一确定的:恰好就是那 k 对两只都在集合里的对。
反过来,给定"哪 k 对完整 + 剩下取哪几只",也能唯一还原出这个集合。
所以三类选择(完整对、单只对、方向)与"合法取法"之间是一一对应,乘法原理可以直接乘——不重不漏。

🧮 样例 2 与两个"必为 0"的边界

样例 2 是 n = 5, m = 1, k = 5:要求 5 对全部完整,那至少要取 2 × 5 = 10 只,可题目只让你取 1 只,显然不可能 → 答案 0。

非法情形判据为什么不可能答案
取不够 2k 只m − 2k < 0每对完整至少要两只,k 对至少 2k 只0
剩余对不够m − 2k > n − k剩下的 n − k 对每对最多贡献 1 只0
1
为什么"每次查询都要先判这两个条件"

r = m − 2k

r < 0:说明 m 连 2k 都不到,直接 0

r > n − k:说明剩下 n − k 对全取单只也不够数

两种情况都不要去调用组合数函数

合法区间是 0 ≤ r ≤ n − k

2
注意 C 函数的自我保护

即使忘了判,也要让 C(a, b) 在 b < 0 或 b > a 时返回 0

否则 fac[b] 会下标越界(b 为负)或算错

层层设防,双保险

✅ 越界也不会 RE

⚠️
两个高频错误:① 少乘 2^r——把"选哪几对各取一只"当成了最终方案,样例 1 会算出 10 × 3 = 30 而不是 120;② 把 m − 2k 写成 m − k——别忘了完整的 k 对是每对两只,消耗的只数是 2k。
04
解法对比
组合公式 + 预处理(正解)vs 每组重新递推组合数

⚔️ 解法对比

🟢 组合公式 + 阶乘逆元预处理(推荐) 推荐

一次预处理阶乘与阶乘逆元到 2000;每组用 C(n,k) · C(n−k, m−2k) · 2^(m−2k) 直接算

  • 预处理 O(2000),每组 O(log m)
  • t = 10⁵ 时总计约 10⁶ 次运算
  • 代码约 35 行
  • 官方题解即此法
💡
正确性来源:"完整对集合"在每组合法取法里是唯一确定的,所以按"完整对 → 单只对 → 左右方向"三分类计数与所有合法取法一一对应,不重不漏。

🟠 每组内部递推 / 暴力枚举

每组用杨辉递推或直接枚举 2n 只手套的子集

  • 杨辉递推每组 O(n²):t = 10⁵ 时必然超时
  • 暴力枚举子集每组 O(2^(2n)),完全不可行
  • 看似省了预处理,代价是把常数放大 10⁵ 倍
  • 还容易在取模处写错
⚠️
为什么慢:t 最大 10⁵,而 n 最大 1000;每组都做一遍 O(n²) 的杨辉三角要 10¹¹ 次运算,离时限差好几个数量级。

📈 性能对比

方案复杂度结论
组合公式 + 预处理O(2000) + O(t log m)✅ 正确,本题正解
每组杨辉递推组合数O(t · n²) ≈ 10¹¹❌ 严重超时
暴力枚举所有子集每组 O(2^(2n))❌ 完全不可行
05
算法流程图
一次预处理 + 每组三步乘法
开始预处理阶乘 fac 与阶乘逆元 invfac(到 2000)读入 t处理每组查询(n, m, k)r = m − 2k0 ≤ r ≤ n − k 吗?是 ✓计算三项乘积否 ✗本组答案为 0ans = C(n, k) × C(n − k, r) × 2^r (mod 10⁹ + 7)还有下一组吗?输出各组答案读下一组 n m k
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧤 手套配对方案数(组合公式)

第一行输入 t,随后 t 行每行输入 n m k。程序会展示每一项组合数的值(均为模 10⁹ + 7 后的结果)与最终答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(组合公式 + 阶乘逆元预处理)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007LL;
const int N = 2005;              // m ≤ 2000,预计算到 2000 足够

ll fac[N], inv_fac[N];

// 快速幂:用于求逆元(MOD 是质数,逆元 = a^(MOD-2))和算 2 的幂
ll qpow(ll a, ll e) {
    ll r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1LL) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

// 组合数 C(a, b)(带越界保护,非法时返回 0)
ll C(int a, int b) {
    if (b < 0 || b > a || a < 0) return 0;
    return fac[a] * inv_fac[b] % MOD * inv_fac[a - b] % MOD;
}

int main() {
    // 1) 预处理阶乘与阶乘逆元:fac[i] = i!,inv_fac[i] = (i!)^(-1)
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
    inv_fac[N - 1] = qpow(fac[N - 1], MOD - 2);          // 费马小定理
    for (int i = N - 1; i >= 1; i--) inv_fac[i - 1] = inv_fac[i] * i % MOD;

    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        int r = m - 2 * k;                               // 还需要"单只"取多少只
        if (r < 0 || r > n - k) {                        // 非法:直接 0
            printf("0\n");
            continue;
        }
        // 2) 三步相乘:选完整对 × 选单只对 × 左右方向
        ll ans = C(n, k) * C(n - k, r) % MOD * qpow(2, r) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}
🔑
三个要点:① 组合数一律先乘再取模,中间结果用 long long(两个 10⁹ 级数相乘约 10¹⁸,刚好在 long long 内);② C 函数自带越界保护,b < 0 或 b > a 时返回 0,这样即使忘了外面判断也不会崩;③ 模数是质数,所以逆元可以用快速幂 a^(p−2) 求。

📖 关键几行怎么看

代码作用为什么这样写
int r = m - 2 * k;剩余只数必须减 2k:每对完整要两只
if (r < 0 || r > n - k)非法短路两种情况都不可能,直接输出 0
C(n, k)选完整对哪 k 对整对取全
C(n - k, r)选单只对剩下 n − k 对里挑 r 对各取一只
qpow(2, r)左右方向被挑中的 r 对各有 2 种取法
inv_fac[N-1] = qpow(fac[N-1], MOD-2);阶乘逆元费马小定理,倒推得到所有逆元
⚠️
五个坑:① 忘记乘 2^r(样例 1 会变 30);② 把 m − 2k 写成 m − k;③ 预处理上界只开到 1000 就够 C(n,k),但为了 n − k 与 r 的余量,开到 2000 更稳;④ 乘法没取模导致 long long 溢出;⑤ 把偶数的 m 与 2k 的比较写成 m < k。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2
5 6 2
5 1 5
120
0
题面样例:正常情况 + 只数不够
1
1000 2000 1000
1上界:全部取完,只有 1 种
1
1000 1500 500
697365585大范围取模,检验阶乘与逆元
1
3 4 1
12C(3,1) × C(2,2) × 2² = 3 × 1 × 4
1
2 2 1
2恰好 1 对完整:2 种(取第 1 对或第 2 对)
1
2 1 1
0m − 2k = −1 < 0,非法短路
1
2 4 2
1全部取完,2 对都完整
1
5 10 5
1上界:n = k,全部取完也只有 1 种
✅
自查清单:① 是 m − 2k 吗?② 乘了 2^(m−2k) 吗?③ 非法情形输出 0 了吗?④ 预处理开到 2000 了吗?

🚨 易错点清单

⚠️
少乘 2^r:被挑中的 r = m − 2k 对,每对还要选左手或右手,样例 1 会从 120 变成 30。
⚠️
减错只数:完整对消耗 2k 只,写成 m − k 就全错。
⚠️
忘记非法短路:m − 2k < 0 或 > n − k 要输出 0,否则组合数会越界。
⚠️
乘法溢出:阶乘、逆元、2 的幂相乘都要边乘边取模,并用 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(2000 + t log m)
空间复杂度
O(2000)
t 上限
10⁵
单组查询
O(log m) 快速幂

时间怎么算的?

空间都用在哪?

两个长度 2005 的 long long 数组(约 32 KB),与 t 无关,属于常数级内存。

✅ 预处理把每组 O(n) 的组合数降到 O(1),是应对 t = 10⁵ 多组询问的标准手段。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「组合数取模」标准预处理模板(模数为质数 p)
const ll MOD = 1000000007LL;
const int N = 2005;

ll fac[N], inv_fac[N];

ll qpow(ll a, ll e) {                 // 快速幂
    ll r = 1 % MOD; a %= MOD;
    while (e > 0) {
        if (e & 1LL) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

void init() {                         // O(N)
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
    inv_fac[N - 1] = qpow(fac[N - 1], MOD - 2);        // 费马小定理求逆元
    for (int i = N - 1; i >= 1; i--) inv_fac[i - 1] = inv_fac[i] * i % MOD;
}

ll C(int a, int b) {                  // O(1) 组合数
    if (b < 0 || b > a || a < 0) return 0;
    return fac[a] * inv_fac[b] % MOD * inv_fac[a - b] % MOD;
}

// 若还要频繁计算 2 的幂,可以再预处理 pow2 数组:
//   pow2[0] = 1;
//   for (int i = 1; i < N; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
// 之后每组查询就是纯 O(1) 了

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
先分类再计数按"完整对 / 单只对 / 方向"三分类,把复杂约束拆成独立步骤取值域、取球、选人配对等组合计数题
组合数取模(质数)阶乘 + 阶乘逆元,O(1) 查询所有需要 C(n, k) mod p 的题(p 为质数)
不可达短路非法条件先判掉,避免越界与无意义计算所有计数题都要做的边界防御
预处理换时间O(N) 预处理换取每组 O(1),应对 t = 10⁵多组询问 + 小值域的通用优化套路
🌟
思考题:如果把要求改成"至少 k 对完整",公式要怎么变?(提示:对完整对数 j = k, k+1, …, n 分别套用本题公式再求和,即 Σⱼ C(n, j) · C(n − j, m − 2j) · 2^(m − 2j);单组求和是 O(n),配合预处理仍能在 1 秒内跑完——"把恰好换成至少,就用求和把恰好枚举一遍"是组合计数最常见的转化。)