简答题 偏难
#21671

奖品分配 时间限制:1.0 s 内存限制:128.0 MB 问题描述 班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有a i…

奖品分配

时间限制:1.0 s

内存限制:128.0 MB

问题描述

班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有ai个(i=0,1,…,M-1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过1个(即:N≤a0+a1+…+aM-1≤N+1)。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对109+7取模后的结果即可。

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

输入描述

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

接下来 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,M,接着是M个正整数a0,a1,…,aM-1。

保证N≤a0+a1+…+aM-1≤N+1。

输出描述

输出T行,每行一个整数,表示该班级分配奖品的方案数对109+7取模的结果。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

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

样例输出 1

3
4
20

样例解释 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 个班级,可以把编号为1的奖品分配给5名同学中的任意一名,共有5种方案;再把编号为2的奖品分配给剩余4名同学中的任意一名,共有4种方案;最后给剩余3名同学自然获得0号奖品。因此,方案数为5×4=20。


样例输入 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

数据规模

对于30%的测试点,保证N≤10。

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

对于所有测试点,保证N≤1000;保证T≤1000;保证M≤1000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int N = 1005; const int mod = 1e9 + 7; int C[N + 5][N + 5], a[N + 5]; void add(int &amp;a, int b) {   a += b;   if (a &gt;= mod)     a -= mod; } void init() {   C[0][0] = 1;   for (int i = 1; i &lt;= N; i++) {     C[i][0] = C[i][i] = 1;     for (int j = 1; j &lt; i; j++)       C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);   } } int main() {   // freopen("data/10.in", "r", stdin);   init();   int T;   scanf("%d", &amp;T);   while (T--) {     int n, m, sum = 0;     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= m; i++)       scanf("%d", &amp;a[i]), sum += a[i];     int ans = 1;     for (int i = 1; i &lt;= m; i++) {       ans = 1ll * ans * C[sum][a[i]] % mod;       sum -= a[i];     }     cout &lt;&lt; ans &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。