GESP 题解库 / 8 级题解 / [GESP202312 八级] 奖品分配 · 第 20 / 24 题
GESP202312 八级 · P10112 · 中等

奖品分配的方案数

多重排列计数:base = N! ÷ Πaᵢ!;若奖品总数是 N + 1,再多乘一个因子 S。

🎁
N ≤ 1000
同学数(T ≤ 1000)
🧮
模 10⁹ + 7
质数模,可求逆元
⚡
O(N + T × M)
一次预计算
🎯
多重排列 + 逆元
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

班上有 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

输入输出样例

样例内容
输入 #13
3 2 1 2
3 2 1 3
5 3 1 3 1
输出 #13
4
20
输入 #25
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99
输出 #21
1
125970
895031741
307187590
💡
人话翻译:把 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,是质数,可求逆元
方案定义只看每位同学拿到哪种奖品;编号相同即视为同种

需要解决的问题

02
思维导图
整理解题思路的全貌
🎁 多重排列公式 + 模 10⁹ + 7 求逆元
🧮 计数模型
只看每位同学拿哪种奖品
同种奖品不可区分 ⇒ 多重排列
S = N:刚好发完
S = N + 1:恰好多 1 个没发出
📐 公式
base = N! ÷ (a₀! × a₁! × … )
S = N 时答案就是 base
S = N + 1 时答案 = base × S
统一写:base × (S == N ? 1 : S)
🔐 模运算
模 10⁹ + 7 是质数
除法一律换成乘逆元
费马小定理 a^(p−2) ≡ a⁻¹
倒推法 O(N) 求出全部逆元
⚠️ 易错点
忘记 S = N + 1 要乘 S
用整数除法导致答案错
阶乘表开得不够大(a₀ 可达 N + 1)
中间乘积没用 long long 溢出
03
样例手算推导
样例 1 三个班级逐一手算 + "为什么多一个奖品就乘 S"

🧮 样例 1:三个班级逐一手算

样例 1 一共三个班级,我们一个一个算清楚。

1
班级 1:N = 3,a = (1, 2),S = 3

奖品总数 3 正好等于同学数 3 ⇒ 所有奖品都要发完

发出的组合:1 个 0 号奖品 + 2 个 1 号奖品

多重排列数式:3! ÷ (1! × 2!) = 6 ÷ 2 = 3

换个说法:从 3 位同学里挑 1 位拿 0 号奖品,C(3, 1) = 3

✅ 3 种方案

2
班级 2:N = 3,a = (1, 3),S = 4

奖品总数 4 = N + 1 ⇒ 恰好多 1 个没发出

先算 base = 3! ÷ (1! × 3!) = 6 ÷ 6 = 1

S = N + 1,因子取 S = 4

答案 = base × 4 = 1 × 4 = 4

✅ 4 种方案

3
班级 3:N = 5,a = (1, 3, 1),S = 5

奖品总数 5 = N ⇒ 全部发完

发出的组合:1 个 0 号、3 个 1 号、1 个 2 号

多重排列数式:5! ÷ (1! × 3! × 1!) = 120 ÷ 6 = 20

也可以这样数:0 号奖品挑 1 位同学(5 种),2 号奖品再挑 1 位(4 种),剩下 3 人自动拿 1 号奖品

✅ 20 种方案

📊 三个班级的汇总

班级Na 序列S = Σaᵢbase = N! ÷ Πaᵢ!因子答案
131, 23 = N313
231, 34 = N + 1144
351, 3, 15 = N20120
🔑
把两行代码记住就够了:base = N! ÷ Πaᵢ!,然后 S == N 就输出 base、S == N + 1 就输出 base × S。
下一节我们把"为什么要乘 S"这个最关键的一步推一遍。

🧮 为什么"S = N + 1"时只多乘一个 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

用班级 2(N = 3、a = (1, 3))验证

剩下的种类 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,两者完全一致 ✓。

1
再验一组:N = 4,a = (1, 1, 1, 2),S = 5 = N + 1

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):

班级Na 序列Sbase(取模后)因子答案
样例2-1100100100 = N111
样例2-2100101101 = N + 19405940661011
样例2-32012, 820 = N1259701125970
样例2-412380, 20, 21, 3124 = N + 1402379291124895031741
样例2-5999101, 234, 499, 66, 99999 = N3071875901307187590
1
看样例2-2:base 其实是 1/101 的"取模替身"

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 号奖品)吻合

2
❌ 如果误用整数除法

100! ÷ 101! 在整数里直接等于 0

整个程序的答案会变成 0

而正确答案是 1

❌ 必须用逆元,不能用整数除法

⚠️
模运算的三条铁律:① 所有的乘法都 % MOD,中间乘积用 long long;② 除法一律换成"乘该数的逆元",本题用费马小定理 a^(p−2),或用倒推法 invFact[i−1] = invFact[i] × i 一次求出全部;③ 上下文中出现的每一个 aᵢ 都满足 aᵢ ≤ N + 1 ≤ 1001 < MOD,所以阶乘一定不会是 MOD 的倍数,逆元必定存在。
04
解法对比
多重排列 + 逆元 vs 大整数硬算 vs 逐位枚举

⚔️ 解法对比

🟢 多重排列 + 逆元(推荐) 推荐

预计算阶乘与逆元表,每组班级算 base = N! ÷ Πaᵢ!,S = N + 1 时再乘 S

  • 预计算 O(N)
  • 每组班级 O(M)
  • 代码约 30 行
  • 官方题解即此思路
💡
正确性来源:S = N 时答案就是多重排列数;S = N + 1 时按"剩下的是第 i 种"分类求和,结果恰好等于 base × S。两类情形合成一个式子,既不重复也不遗漏。

🟠 大整数硬算 / 逐位枚举

用大整数算出精确的组合数再取模;或枚举每位同学拿哪种奖品

  • 枚举法:指数级,完全不可行
  • 大整数:N = 1000 时数字有上千位
  • 最后仍要对 10⁹ + 7 取模
  • 常数巨大,写法也不优雅
⚠️
它们为什么会挂:方案数随 N 迅速膨胀,必须边算边取模;一旦取模,"除法"就不存在了,只能乘逆元。所以"先算精确值再取模"既慢又绕,直接用模运算 + 逆元才是正路。

📈 性能对比

方案复杂度结论
多重排列 + 逆元O(N + T × M)✅ 正确且最快,官方思路
大整数算完再取模O(N × 大整数位数)⚠️ 答案对但常数大,纯属绕远路
枚举每位同学拿哪种指数级❌ 完全不可行
05
算法流程图
预计算阶乘 + 逐班级套公式 主流程
开始读入 T;预计算 fact[0 … 1001] 与对应的逆元表循环:处理第 i 个班级(i = 1 … T)读入 N、M 与 a₀、a₁、…、a_{M−1}S = Σaᵢ;base = fact[N] × Π invFact[aᵢ] mod pS 比 N 多出几个奖品?多 0 个 ✓因子取 1多 1 个 ✗因子取 Sans = base × 因子 mod p,输出该班级的答案T 个班级全部输出完毕下一个班级
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎁 方案数计算器(多重排列 + 逆元)

第一行输入 T;随后 T 行每行输入 N M a₀ … a_{M−1}(需满足 N ≤ Σaᵢ ≤ N + 1)。程序会逐组展示 S、base、因子与最终答案(对 10⁹ + 7 取模)。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(多重排列 + 费马小定理求逆元)

#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。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
3
3 2 1 2
3 2 1 3
5 3 1 3 1
3
4
20
题面样例 1(S = N 与 S = N + 1 各出现)
1
100 1 101
1S = N + 1 的极端情形:101 个同种奖品,方案只有 1 种
1
123 4 80 20 21 3
895031741题面样例 2 第 4 组(必须取模)
1
999 5 101 234 499 66 99
307187590题面样例 2 第 5 组:S = N,纯多重排列
1
1 1 1
1最小规模:N = 1,S = 1 = N
2
1 1 2
2 2 1 2
1
3
两组小规模 S = N + 1(1! ÷ 2! × 2 = 1、2! ÷ 2! × 3 = 3)
1
3 2 2 2
6S = N + 1:3! ÷ (2! × 2!) × 4 = 6,因子来自"剩下哪一个"
✅
自查清单:① 有 base = N! ÷ Πaᵢ! 吗?② 有 S == N + 1 的特判吗?③ 除法全换成逆元了吗?④ 中间量是 long long 吗?⑤ 阶乘表开到 1001 以上了吗?

🚨 易错点清单

⚠️
忘记 S == N + 1 要乘 S:样例 1 的第 2 组会输出 1 而不是 4。
⚠️
用整数除法代替逆元:模运算下数值已被打散,/ 只会得到错误结果,必须乘逆元。
⚠️
中间乘积用 int:10⁹ × 10⁹ 远超 2 × 10⁹,必须 long long。
⚠️
阶乘表开小了:M = 1 时 a₀ 可达 N + 1,表要开到 1001 以上。
⚠️
把 S 当成 N 写死:S 要由读入的 aᵢ 累加得到。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N + T × M + log p)
空间复杂度
O(N)
预计算
一次阶乘 + 一次快速幂
每次求逆元
O(log p) ≈ 30 步

时间怎么算的?

空间都用在哪?

两个长度为 1005 的 long long 数组(fact 与 invFact)合计约 16 KB;此外只用到几个循环变量,空间 O(N),几乎可以忽略。

✅ 约 10⁶ 次模乘,运行时间可以忽略不计。N ≤ 1000 这个条件非常小,所以"预计算阶乘表 + 逆元表"是最省事、最稳妥的写法。

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

🔗 常用技巧小抄

// ---------- 多重排列计数通用模板 ----------
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 之间二选一。
如果改成"剩余奖品不超过 2 个"(S ≤ N + 2),还能这么算吗?(提示:多出的 2 个奖品要么来自同一种(数量减 2),要么来自两种各一个——需要把这两类情形分开枚举,此时答案不再是简单地乘一个常数,而要写成更细的分类求和。
把"分类讨论"做细,是计数题永远的主线。)