当前位置: 首页 > news >正文

洛谷P10112 [GESP202312 八级] 奖品分配

传送门

原题

题目描述

班上有 \(N\) 名同学,学号从 \(0\)\(N-1\)。有 \(M\) 种奖品要分给这些同学,其中,第 \(i\) 种奖品总共有 \(a_i\) 个 (\(i=0,1, \cdots ,M-1\))。

巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过 \(1\) 个(即:\(N\le a_0+a_1+ \cdots +a_{M-1}\le N+1\))。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对 \(10^{9}+7\) 取模后的结果即可。

共有 \(T\) 个班级都面临着奖品分配的问题,你需要依次为他们解答。

输入格式

第一行一个整数 \(T\),表示班级数量。

接下来 \(T\) 行,每行若干用单个空格隔开的正整数。首先是两个正整数\(N,M\),接着是 \(M\) 个正整数 \(a_0,a_1...a_{M-1}\)。保证 $N \le a_0+a_1+\cdots+a_{M-1} \le N+1 $。

输出格式

输出 \(T\) 行,每行一个整数,表示该班级分配奖品的方案数对 \(10^{9}+7\) 取模的结果。

输入输出样例 #1

输入 #1

3
3 2 1 2
3 2 1 3
5 3 1 3 1

输出 #1

3
4
20

输入输出样例 #2

输入 #2

5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99

输出 #2

1
1
125970
895031741
307187590

说明/提示

样例解释 1

对于第 \(1\) 个班级,学号为 \(0,1,2\) 的同学可以依次分别获得奖品 \(0,1,1\),也可以依次分别获得奖品 \(1,0,1\),也可以依次分别获得奖品 \(1,1,0\) ,因此共有 \(3\) 种方案。

对于第 \(2\) 个班级,学号为 \(0,1,2\) 的同学可以依次分别获得奖品 \(0,1,1\) ,也可以依次分别获得奖品 \(1,0,1\),也可以依次分别获得奖品 \(1,1,0\),也可以依次分别获得奖品 \(1,1,1\),因此共有 \(4\) 种方案。

对于第 \(3\) 个班级,可以把编号为 \(0\) 的奖品分配给 \(5\) 名同学中的任意一名,共有 \(5\) 种方案;再把编号为 \(2\) 的奖品分配给剩余 \(4\) 名同学中的任意一名,共有\(4\) 种方案;最后给剩余 \(3\) 名同学自然获得 \(1\) 号奖品。因此,方案数为 \(5 \times 4 = 20\)

数据范围

对于 \(30\%\) 的测试点,保证 \(N \le 10\)

对于另外 \(30\%\) 的测试点,保证 \(M=2\)

对于所有测试点,保证 \(N \le 1000\);保证 \(T \le 1000\) ;保证 \(M \le 1001\)

整理&思路

因为每个人只要一个奖品,所以我们按奖品分类。
假设我们一共有\(sum\)个奖品,针对第\(i\)种奖品,我们需要有\(a_{i}\)个小朋友来拿走奖品,而根据组合数可得:

\[f(i) = C\binom{a_{i}}{sum} \]

而所有的奖品的总组合数就是:

\[ans = \prod_{i=1}^{m} C\binom{a_{i}}{sum} \]

当然,此时的\(sum\)是不断改变的,每取一次\(sum\)就要减少一次\(a_{i}\)

然而,常规的组合数肯定是会崩的,这时候就要请出杨辉三角了:

\[C\binom ij = C\binom {i-1}j + C\binom i{j-1} \]

当然,\(j\leq i\)\(j=1时C \binom ij=1\)

当然,你还需要做这样的一个处理:

sum = n + (sum>n);

以确保分配的时候有一个或零个剩余。

AC代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn = 1010;
const int mod = 1e9 + 7;int a[maxn], C[maxn][maxn];//杨辉三角
void init() {for (int i = 0; i < maxn; i++) {for (int j = 0; j <= i; j++) {if (j == 0 || j == i) C[i][j] = 1;else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}}
}
signed main() {init();int T;scanf("%lld", &T);while(T--) {int n, m;scanf("%lld%lld", &n, &m);int sum = 0;for (int i = 1; i <= m; i++) {scanf("%d", &a[i]);sum += a[i];}sum=n+(sum>n);int ans = 1;for (int i = 1; i <= m; i++) {ans = (ans * C[sum][a[i]]) % mod; // 分配礼物的组合方法sum -= a[i]; // 分配一次礼物就减少一次}printf("%lld\n", ans);}return 0;
}

恭喜AC!

http://www.hskmm.com/?act=detail&tid=20073

相关文章:

  • P10400 『STA - R5』消失的计算机
  • 2025 地坪研磨机厂家推荐权威推荐排行榜:品牌深度解析及格力 / 宁德时代合作案例速递水磨石/遥控式/座驾式/小型地坪研磨机厂家推荐
  • 2025 年最新推荐铝塑膜源头厂家权威排行榜:聚焦 3000㎡厂房与完整产业链的优质企业盘点复合/防锈防潮/木箱包装/设备包装铝塑膜厂家推荐
  • 2025 年真空袋生产厂家最新权威推荐排行榜:TOP 级企业工艺、服务及适配场景全景对比指南木箱/设备/海运防潮/铝塑/电柜真空袋厂家推荐
  • 《码界飞升传II:数据星辰异界问道》
  • Win FAQ
  • 结论(数学)
  • loki收集容器日志
  • Xcode 火焰图
  • 完整教程:dlib库关键点定位和疲劳检测
  • 2025 长沙美食餐厅权威推荐排行榜:老店红记领衔新晋品牌,200 + 湘味与网红菜品深度解析,吃货必藏指南长沙美食湘菜馆 /大排档/网红店餐厅推荐
  • VKD233HH触控IC有两种输出方式“直接输出”和“锁存输出”单路触摸检测芯片
  • 打包present, but unavailable
  • 2025 年最新推荐环保门禁厂家权威排行榜:清洁运输 / 智能 / 移动源系统及电子台账厂商详析企业/智能环保门禁厂家推荐
  • 2025 年即时通讯公司推荐 小天互连:私有化部署即时通讯、信创即时通讯、国产化即时通讯、局域内网即时通讯、企业 IM 即时通讯解决方案解析
  • GJOI 模拟赛6、7部分题解
  • 【C++list】底层结构、迭代器核心原理与常用接口完成全解析
  • 完整教程:Flink Watermark机制解析
  • 2025 年北京湖南菜餐厅推荐:小湖南岸以湖湘本味与匠心服务,成京城湘菜口碑之选
  • Vector
  • SSM
  • Mybatis Plus
  • 0927模拟赛总结
  • AT_agc010_b [AGC010B] Boxes
  • Selenium自动化脚本总报错?这7个调试技巧帮你解决90%问题
  • C语言 - *进制转*进制 3
  • ThreadLocal详解
  • C语言 - *进制转*进制 2
  • Functions
  • QOJ #5421. Factories Once More 题解