Description
JYY 带队参加了若干场ACM/ICPC 比赛,带回了许多土特产,要分给实验室的同学们。
JYY 想知道,把这些特产分给N 个同学,一共有多少种不同的分法?当然,JYY 不希望任何一个同学因为没有拿到特产而感到失落,所以每个同学都必须至少分得一个特产。
例如,JYY 带来了2 袋麻花和1 袋包子,分给A 和B 两位同学,那么共有4 种不同的分配方法:
A:麻花,B:麻花、包子
A:麻花、麻花,B:包子
A:包子,B:麻花、麻花
A:麻花、包子,B:麻花
Input
输入数据第一行是同学的数量N 和特产的数量M。
第二行包含M 个整数,表示每一种特产的数量。
N, M 不超过1000,每一种特产的数量不超过1000
Output
输出一行,不同分配方案的总数。由于输出结果可能非常巨大,你只需要输出最终结果MOD 1,000,000,007 的数值就可以了。
Sample Input
5 4
1 3 3 5
1 3 3 5
Sample Output
384835
题解
想到了隔板法,想到了容斥...就是不知道怎么写...
对于总共$n$个人,很容易想到第$i$个物品,分出的方案数为$C^{n-1} _{a[i]+n-1}$,其中$a[i]$为个数(隔板法)。
但是这样做就会导致有人分不到特产。
考虑容斥,我们-一个人分不到的情况+两个人分不到的情况-三个人...
我们直接限定隔板的数目来强制一些人分不到特产,即方案数变为$C^{n-1-i} _{a[j]+n-1-i}$,其中$i$个人强制分不到,第$j$个物品。
注意最后,因为分不到的人可以是任意的,所以每次容斥还要*$C^i _n$。
//It is made by Awson on 2017.9.25
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define LL long long
using namespace std;
const int N = ;
const int MOD = ; int n, m, mx;
int a[N+];
int C[N*+][N*+]; void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= m; i++) {
scanf("%d", &a[i]);
mx = Max(mx, a[i]);
}
mx += n;
for (int i = ; i <= mx; i++) {
C[i][] = ;
for (int j = ; j <= i; j++)
C[i][j] = (C[i-][j-]+C[i-][j])%MOD;
}
LL ans = ;
for (int i = ; i < n; i++) {
LL cnt = ;
for (int j = ; j <= m; j++)
cnt = cnt*C[a[j]+n--i][n--i]%MOD;
cnt = cnt*C[n][i]%MOD;
if (i%) ans = (ans+MOD-cnt)%MOD;
else ans = (ans+cnt)%MOD;
}
printf("%lld\n", ans);
}
int main() {
work();
return ;
}