Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 96 Solved: 62
[Submit][Status][Discuss]
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
HINT
Source
数学问题 组合数 容斥
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int mxn=;
const int mod=1e9+;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
LL fac[mxn],inv[mxn];
void init(){
fac[]=fac[]=;
inv[]=inv[]=;
for(int i=;i<mxn;i++){
fac[i]=(LL)fac[i-]*i%mod;
inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod;
}
for(int i=;i<mxn;i++)
inv[i]=(LL)inv[i]*inv[i-]%mod;
return;
}
LL calc(int n,int m){
if(!m)return ;
if(n<m)return ;
return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,m;
int a[mxn],smm=;
LL f[mxn];
int main(){
int i,j;
init();
n=read();m=read();
for(i=;i<=m;i++)
a[i]=read();
for(i=;i<=n;i++){
f[i]=;
for(j=;j<=m;j++)
f[i]=f[i]*calc(i-+a[j],a[j])%mod;
for(j=;j<i;j++){
f[i]=(f[i]-f[j]*calc(i,j)%mod+mod)%mod;
}
}
printf("%lld\n",f[n]);
return ;
}