先选定"被取全的 k 对",剩下的每对至多取一只,再乘上左右手的 2 种选法。
小杨有 n 对不同的手套,每对手套由左右各一只组成。
小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。
小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。
本题单个测试点内有多组测试数据。第一行一个正整数 t,代表测试用例组数。
接下来 t 组测试用例,每组一行,包含三个正整数 n, m, k,代表手套对数、取出的手套数和目标对数。
对于每组测试数据,输出一个整数,代表可能的情况数量对 10⁹ + 7 取模的结果。
| 样例 | 输入 | 输出 |
|---|---|---|
| #1 | 25 6 25 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% 全范围 |
2n 只做组合会把"哪些对完整"数重复。先按"完整对"做一次分类选择 C(n, k),剩下的部分就只剩"单只"这一种形态,非常干净k 对完整。若剩下的某一对被取了两只,完整对数就变成 k + 1,不符合题意2^(m − 2k) 是怎么来的?被挑中的 m − 2k 对,每对必须且只能贡献一只,而这一只可以是左手也可以是右手,每对 2 种选法、彼此独立 → 由乘法原理得 2^(m − 2k)m − 2k < 0(要取全 k 对至少需要 2k 只);m − 2k > n − k(剩下的对数不够凑齐剩余只数)。此时直接输出 0t 可达 10⁵,若每组都用 O(n) 递推求组合数,总复杂度 10⁸ 量级容易超时;预处理一次阶乘与阶乘逆元到 2000,之后每次查询 O(1) 取 C、O(log m) 求 2 的幂把 5 对手套编号为 1…5,每对记为 i左 / i右,共 10 只。要取 6 只,恰好 2 对完整。
从 5 对里挑 2 对:C(5, 2) = 10
这 2 对的左右两只都要拿,共 4 只
例如选定 {1, 3},则 1左、1右、3左、3右 都进集合
第一步 10 种
总共要取 6 只,已经用掉 4 只 → 还差 r = 6 − 4 = 2 只
剩余可用对是 3 对,每对最多取 1 只
先挑出"要贡献一只"的 2 对:C(3, 2) = 3
例如剩余对是 {2, 4, 5},挑 {2, 5}
第二步 3 种
被挑中的 2 对,每对 2 种选择(左 / 右)
2 × 2 = 2² = 4
例如 2左 & 5右、2右 & 5左、2左 & 5左、2右 & 5右
第三步 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 是 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 |
r = m − 2k
r < 0:说明 m 连 2k 都不到,直接 0
r > n − k:说明剩下 n − k 对全取单只也不够数
两种情况都不要去调用组合数函数
合法区间是 0 ≤ r ≤ n − k
即使忘了判,也要让 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。一次预处理阶乘与阶乘逆元到 2000;每组用 C(n,k) · C(n−k, m−2k) · 2^(m−2k) 直接算
每组用杨辉递推或直接枚举 2n 只手套的子集
10⁵,而 n 最大 1000;每组都做一遍 O(n²) 的杨辉三角要 10¹¹ 次运算,离时限差好几个数量级。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 组合公式 + 预处理 | O(2000) + O(t log m) | ✅ 正确,本题正解 |
| 每组杨辉递推组合数 | O(t · n²) ≈ 10¹¹ | ❌ 严重超时 |
| 暴力枚举所有子集 | 每组 O(2^(2n)) | ❌ 完全不可行 |
第一行输入 t,随后 t 行每行输入 n m k。程序会展示每一项组合数的值(均为模 10⁹ + 7 后的结果)与最终答案。
点按钮开始 →
#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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | 120 0 | 题面样例:正常情况 + 只数不够 |
1 | 1 | 上界:全部取完,只有 1 种 |
1 | 697365585 | 大范围取模,检验阶乘与逆元 |
1 | 12 | C(3,1) × C(2,2) × 2² = 3 × 1 × 4 |
1 | 2 | 恰好 1 对完整:2 种(取第 1 对或第 2 对) |
1 | 0 | m − 2k = −1 < 0,非法短路 |
1 | 1 | 全部取完,2 对都完整 |
1 | 1 | 上界:n = k,全部取完也只有 1 种 |
m − 2k 吗?② 乘了 2^(m−2k) 吗?③ 非法情形输出 0 了吗?④ 预处理开到 2000 了吗?r = m − 2k 对,每对还要选左手或右手,样例 1 会从 120 变成 30。2k 只,写成 m − k 就全错。m − 2k < 0 或 > n − k 要输出 0,否则组合数会越界。long long。两个长度 2005 的 long long 数组(约 32 KB),与 t 无关,属于常数级内存。
✅ 预处理把每组 O(n) 的组合数降到 O(1),是应对 t = 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 秒内跑完——"把恰好换成至少,就用求和把恰好枚举一遍"是组合计数最常见的转化。)