多重排列计数:base = N! ÷ Πaᵢ!;若奖品总数是 N + 1,再多乘一个因子 S。
班上有 N 名同学,学号从 0 到 N − 1。有 M 种奖品要分给这些同学,其中,第 i 种奖品总共有 aᵢ 个(i = 0, 1, …, M − 1)。
巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过 1 个(即:N ≤ a₀ + a₁ + … + a_{M−1} ≤ N + 1)。
现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。
只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对 10⁹ + 7 取模后的结果即可。
共有 T 个班级都面临着奖品分配的问题,你需要依次为他们解答。
| 项目 | 说明 |
|---|---|
| 输入第一行 | 一个整数 T,表示班级数量 |
| 接下来 T 行 | 每行若干用单个空格隔开的正整数。首先是两个正整数 N, M,接着是 M 个正整数 a₀, a₁, …, a_{M−1} |
| 数据保证 | N ≤ a₀ + a₁ + … + a_{M−1} ≤ N + 1 |
| 输出 | T 行,每行一个整数,表示该班级方案数对 10⁹ + 7 取模的结果 |
| 部分分 | 30% 数据 N ≤ 10;另有 30% 数据 M = 2 |
| 数据范围 | N ≤ 1000,T ≤ 1000,M ≤ 1001 |
| 样例 | 内容 |
|---|---|
| 输入 #1 | 3 |
| 输出 #1 | 3 |
| 输入 #2 | 5 |
| 输出 #2 | 1 |
S = Σaᵢ 个奖品发下去,每位同学恰好拿一个,问"每位同学拿到的是哪一种"有多少种可能。同一种奖品之间完全一样,所以这正是一个"带重复元素的排列"(多重排列)问题。关键观察:S 只有两种取值,分别对应两种情况:
S = N:奖品刚好发完,每一种奖品都得发干净;S = N + 1:恰好多出 1 个没发出去,而它只能是某一种里的一个——于是枚举"剩下的是哪一种",把结果加起来。模数 10⁹ + 7 是质数,所以公式里的除法可以换成"乘逆元"。
多重排列组合计数分类讨论模 10⁹ + 7费马小定理求逆元
| 项目 | 说明 |
|---|---|
| 同学数 | N ≤ 1000,学号 0 … N − 1 |
| 奖品种类 | M ≤ 1001,第 i 种有 aᵢ ≥ 1 个 |
| 奖品总数 | S = Σaᵢ 满足 N ≤ S ≤ N + 1 |
| 班级数 | T ≤ 1000,各班级相互独立 |
| 取模 | 10⁹ + 7,是质数,可求逆元 |
| 方案定义 | 只看每位同学拿到哪种奖品;编号相同即视为同种 |
N! ÷ (a₀! × a₁! × … × a_{M−1}!)S = N 时就是这个式子?此时所有奖品都被发出,发出的组合恰好是"a₀ 个 0 号、a₁ 个 1 号……",多重排列公式直接给出答案S = N + 1 时只多乘一个 S?恰好多 1 个没发出,设剩下的是第 i 种,则该情形方案数是 N! ÷ ((aᵢ − 1)! × Π aⱼ!)(j 取遍除 i 外的下标)。把它改写成 base × aᵢ(base = N! ÷ (aᵢ! × Π aⱼ!)),再对 i 求和就得到 base × Σaᵢ = base × S10⁹ + 7 是质数,a^(p−2) mod p 就是 a 的逆元N ≤ 1000 非常小,阶乘表与逆元表各一千多项,一次算好之后所有班级共用,每组班级只剩 O(M) 次乘法样例 1 一共三个班级,我们一个一个算清楚。
奖品总数 3 正好等于同学数 3 ⇒ 所有奖品都要发完
发出的组合:1 个 0 号奖品 + 2 个 1 号奖品
多重排列数式:3! ÷ (1! × 2!) = 6 ÷ 2 = 3
换个说法:从 3 位同学里挑 1 位拿 0 号奖品,C(3, 1) = 3
✅ 3 种方案
奖品总数 4 = N + 1 ⇒ 恰好多 1 个没发出
先算 base = 3! ÷ (1! × 3!) = 6 ÷ 6 = 1
S = N + 1,因子取 S = 4
答案 = base × 4 = 1 × 4 = 4
✅ 4 种方案
奖品总数 5 = N ⇒ 全部发完
发出的组合:1 个 0 号、3 个 1 号、1 个 2 号
多重排列数式:5! ÷ (1! × 3! × 1!) = 120 ÷ 6 = 20
也可以这样数:0 号奖品挑 1 位同学(5 种),2 号奖品再挑 1 位(4 种),剩下 3 人自动拿 1 号奖品
✅ 20 种方案
| 班级 | N | a 序列 | S = Σaᵢ | base = N! ÷ Πaᵢ! | 因子 | 答案 |
|---|---|---|---|---|---|---|
| 1 | 3 | 1, 2 | 3 = N | 3 | 1 | 3 |
| 2 | 3 | 1, 3 | 4 = N + 1 | 1 | 4 | 4 |
| 3 | 5 | 1, 3, 1 | 5 = N | 20 | 1 | 20 |
base = N! ÷ Πaᵢ!,然后 S == N 就输出 base、S == N + 1 就输出 base × S。S = N + 1 意味着恰好多出 1 个奖品没发出去。设剩下的是第 i 种奖品,那么实际发出去的是第 i 种的 aᵢ − 1 个,加上其它种类的全部——总数正好是 N 个,刚好每人一个。
对固定的 i,方案数是多重排列:
N! ÷ ( (aᵢ − 1)! × Π aⱼ! ) = [ N! ÷ ( aᵢ! × Π aⱼ! ) ] × aᵢ = base × aᵢ
其中 Π aⱼ! 表示"除第 i 种以外所有种类的阶乘之积",关键一步是把 aᵢ! 拆成 aᵢ × (aᵢ − 1)!,于是多出来的那个 aᵢ 就"浮"到了括号外面。
把 i 从 0 到 M − 1 全加起来(这些情形两两不重复,因为"剩下哪一种"必然唯一):
Σᵢ (base × aᵢ) = base × Σᵢ aᵢ = base × S
| 剩下的种类 i | 实际发出的组合 | 该情形的方案数 |
|---|---|---|
| i = 0(剩下 1 个 0 号奖品) | 0 个 0 号、3 个 1 号 | 3! ÷ (0! × 3!) = 6 ÷ 6 = 1 |
| i = 1(剩下 1 个 1 号奖品) | 1 个 0 号、2 个 1 号 | 3! ÷ (1! × 2!) = 6 ÷ 2 = 3 |
合计 1 + 3 = 4;而公式这边 base × S = 1 × 4 = 4,两者完全一致 ✓。
base = 4! ÷ (1! × 1! × 1! × 2!) = 24 ÷ 2 = 12
公式给出 12 × 5 = 60
暴力枚举"剩下哪一种":
剩下一个 2 号奖品:4! ÷ (1! × 1! × 1! × 1!) = 24
剩下第 1 个 1 号奖品:4! ÷ (0! × 1! × 1! × 2!) = 12
另外两个 1 号奖品各对称地给出 12
合计 24 + 12 + 12 + 12 = 60
✅ 与 base × S = 60 完全一致
S 种,而每一种对应的基础排列数都是同一个 base,所以总数就是 base × S。base × (S == N ? 1 : S),既不用分类讨论,也不会漏算。样例 2 的第 4、5 组必须取模,顺手看看取模前后的差别(第 5 组 S = 999 = N):
| 班级 | N | a 序列 | S | base(取模后) | 因子 | 答案 |
|---|---|---|---|---|---|---|
| 样例2-1 | 100 | 100 | 100 = N | 1 | 1 | 1 |
| 样例2-2 | 100 | 101 | 101 = N + 1 | 940594066 | 101 | 1 |
| 样例2-3 | 20 | 12, 8 | 20 = N | 125970 | 1 | 125970 |
| 样例2-4 | 123 | 80, 20, 21, 3 | 124 = N + 1 | 402379291 | 124 | 895031741 |
| 样例2-5 | 999 | 101, 234, 499, 66, 99 | 999 = N | 307187590 | 1 | 307187590 |
N = 100、a = (101):真正的 base = 100! ÷ 101! = 1 ÷ 101
它不是整数,但模意义下
940594066 × 101 ≡ 1 (mod 10⁹ + 7)
所以 940594066 就是 101 的逆元
答案 = base × S = 940594066 × 101 mod p = 1
✅ 与实际只有 1 种方案(人人拿 0 号奖品)吻合
100! ÷ 101! 在整数里直接等于 0
整个程序的答案会变成 0
而正确答案是 1
❌ 必须用逆元,不能用整数除法
% MOD,中间乘积用 long long;② 除法一律换成"乘该数的逆元",本题用费马小定理 a^(p−2),或用倒推法 invFact[i−1] = invFact[i] × i 一次求出全部;③ 上下文中出现的每一个 aᵢ 都满足 aᵢ ≤ N + 1 ≤ 1001 < MOD,所以阶乘一定不会是 MOD 的倍数,逆元必定存在。预计算阶乘与逆元表,每组班级算 base = N! ÷ Πaᵢ!,S = N + 1 时再乘 S
S = N 时答案就是多重排列数;S = N + 1 时按"剩下的是第 i 种"分类求和,结果恰好等于 base × S。两类情形合成一个式子,既不重复也不遗漏。用大整数算出精确的组合数再取模;或枚举每位同学拿哪种奖品
N = 1000 时数字有上千位10⁹ + 7 取模N 迅速膨胀,必须边算边取模;一旦取模,"除法"就不存在了,只能乘逆元。所以"先算精确值再取模"既慢又绕,直接用模运算 + 逆元才是正路。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 多重排列 + 逆元 | O(N + T × M) | ✅ 正确且最快,官方思路 |
| 大整数算完再取模 | O(N × 大整数位数) | ⚠️ 答案对但常数大,纯属绕远路 |
| 枚举每位同学拿哪种 | 指数级 | ❌ 完全不可行 |
第一行输入 T;随后 T 行每行输入 N M a₀ … a_{M−1}(需满足 N ≤ Σaᵢ ≤ N + 1)。程序会逐组展示 S、base、因子与最终答案(对 10⁹ + 7 取模)。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007LL; // 质数,所以能求逆元 const int MAXN = 1005; // N ≤ 1000 且 a_i ≤ N + 1 ≤ 1001 ll fact[MAXN], invFact[MAXN]; // 快速幂:算 a^b mod MOD(费马小定理求逆元时 b = MOD - 2) ll qpow(ll a, ll b) { ll r = 1; while (b) { if (b & 1) r = r * a % MOD; // 中间乘积用 long long,别用 int a = a * a % MOD; b >>= 1; } return r; } int main() { fact[0] = 1; for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD; // 只做一次快速幂,就得到最大阶乘的逆元 invFact[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2); // 再倒推:1/(i-1)! = (1/i!) * i,O(N) 求出全部逆元 for (int i = MAXN - 1; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD; int T; scanf("%d", &T); while (T--) { int N, M; scanf("%d %d", &N, &M); ll base = fact[N], S = 0; // base 从 N! 开始 for (int i = 0; i < M; i++) { int a; scanf("%d", &a); S += a; // 顺便累计奖品总数 base = base * invFact[a] % MOD; // ÷ a! 等价于 × invFact[a] } if (S == N + 1) base = base * (S % MOD) % MOD; // 恰好多 1 个奖品 printf("%lld\n", base); } return 0; }
O(N) 推完;③ 别忘记 S == N + 1 时要乘上因子 S。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
fact[i] = fact[i-1] * i % MOD; | 阶乘递推 | N ≤ 1000 很小,一次算好,所有班级共用 |
invFact[MAXN-1] = qpow(fact[MAXN-1], MOD-2); | 求最大阶乘的逆元 | MOD 是质数 ⇒ a^(p−2) ≡ a⁻¹ |
invFact[i-1] = invFact[i] * i % MOD; | 倒推全部逆元 | 由 1/(i−1)! = (1/i!) × i 得到,省掉 N 次快速幂 |
base = base * invFact[a] % MOD; | 除以 a! | 用乘逆元代替除法,这才是模运算的正确姿势 |
if (S == N + 1) base = base * (S % MOD) % MOD; | 多一个奖品的情形 | 枚举"剩下哪一种"求和后,恰好等于乘上 S |
S == N + 1,答案会偏小;② 用 / 做取模后的除法(数值已经打散,必须用逆元);③ 中间乘积用 int(10⁹ × 10⁹ 会溢出,必须 long long);④ 阶乘表只开到 N:当 M = 1 时 a₀ 可能是 N + 1,会越界;⑤ S 必须用读入的 aᵢ 累加得到,不要想当然地认为它一定等于 N。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 3 4 20 | 题面样例 1(S = N 与 S = N + 1 各出现) |
1 | 1 | S = N + 1 的极端情形:101 个同种奖品,方案只有 1 种 |
1 | 895031741 | 题面样例 2 第 4 组(必须取模) |
1 | 307187590 | 题面样例 2 第 5 组:S = N,纯多重排列 |
1 | 1 | 最小规模:N = 1,S = 1 = N |
2 | 1 3 | 两组小规模 S = N + 1(1! ÷ 2! × 2 = 1、2! ÷ 2! × 3 = 3) |
1 | 6 | S = N + 1:3! ÷ (2! × 2!) × 4 = 6,因子来自"剩下哪一个" |
base = N! ÷ Πaᵢ! 吗?② 有 S == N + 1 的特判吗?③ 除法全换成逆元了吗?④ 中间量是 long long 吗?⑤ 阶乘表开到 1001 以上了吗?S == N + 1 要乘 S:样例 1 的第 2 组会输出 1 而不是 4。/ 只会得到错误结果,必须乘逆元。10⁹ × 10⁹ 远超 2 × 10⁹,必须 long long。M = 1 时 a₀ 可达 N + 1,表要开到 1001 以上。S 当成 N 写死:S 要由读入的 aᵢ 累加得到。O(N),N ≤ 1000O(log p) ≈ 30 步O(N),比做 N 次快速幂快得多M 个数并各乘一次 invFact[aᵢ],共 O(M)T × M ≤ 1000 × 1001 ≈ 10⁶ 次乘法,完全在 1 秒之内两个长度为 1005 的 long long 数组(fact 与 invFact)合计约 16 KB;此外只用到几个循环变量,空间 O(N),几乎可以忽略。
✅ 约 10⁶ 次模乘,运行时间可以忽略不计。N ≤ 1000 这个条件非常小,所以"预计算阶乘表 + 逆元表"是最省事、最稳妥的写法。
// ---------- 多重排列计数通用模板 ---------- const ll MOD = 1000000007LL; // 必须是质数才能用费马小定理 const int MAXN = 1005; ll fact[MAXN], invFact[MAXN]; ll qpow(ll a, ll b){ ll r = 1; while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; } return r; } // ① 阶乘表 fact[0] = 1; for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD; // ② 逆元表(一次快速幂 + 倒推) invFact[MAXN-1] = qpow(fact[MAXN-1], MOD - 2); for (int i = MAXN-1; i >= 1; i--) invFact[i-1] = invFact[i] * i % MOD; // ③ 组合数 / 多重排列 ll C(int n, int k){ // 组合数 C(n, k) if (k < 0 || k > n) return 0; return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD; } ll multiPerm(int n, vector<int> a){ // N! / (a0! * a1! * ...) ll r = fact[n]; for (int x : a) r = r * invFact[x] % MOD; return r; } // ---------- 本题的收尾 ---------- // S = sum(a);若 S == N + 1,再乘上 S 即可
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 多重排列 | N! ÷ (a₀! × a₁! × …) | "相同元素不可区分"的一切计数问题 |
| 分类求和 | 把"剩下的是第 i 种"求和,化简成乘一个 S | "恰好少用掉一个"的多物品分配问题 |
| 模逆元 | 用 a^(p−2) 代替除法 | 一切模质数下的组合数计算 |
| 线性倒推逆元 | 由 1/(i−1)! = (1/i!) × i 求出全部 | 需要大量阶乘逆元时的标准优化 |
| 一次预计算 + 多组询问 | 每问只做 O(M) 次乘法 | T 组独立数据的"预处理 → 查询"模式 |
1 个,所以公式只在 S = N 与 S = N + 1 之间二选一。S ≤ N + 2),还能这么算吗?(提示:多出的 2 个奖品要么来自同一种(数量减 2),要么来自两种各一个——需要把这两类情形分开枚举,此时答案不再是简单地乘一个常数,而要写成更细的分类求和。