首页 > 代码库 > Bzoj4710 [Jsoi2011]分特产
Bzoj4710 [Jsoi2011]分特产
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
数学问题 组合数 容斥
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define LL long long 6 using namespace std; 7 const int mxn=2011; 8 const int mod=1e9+7; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}13 return x*f;14 }15 LL fac[mxn],inv[mxn];16 void init(){17 fac[0]=fac[1]=1;18 inv[0]=inv[1]=1;19 for(int i=2;i<mxn;i++){20 fac[i]=(LL)fac[i-1]*i%mod;21 inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod;22 }23 for(int i=2;i<mxn;i++)24 inv[i]=(LL)inv[i]*inv[i-1]%mod;25 return;26 }27 LL calc(int n,int m){28 if(!m)return 1;29 if(n<m)return 0;30 return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;31 }32 int n,m;33 int a[mxn],smm=0;34 LL f[mxn];35 int main(){36 int i,j;37 init();38 n=read();m=read();39 for(i=1;i<=m;i++)40 a[i]=read();41 for(i=1;i<=n;i++){42 f[i]=1;43 for(j=1;j<=m;j++)44 f[i]=f[i]*calc(i-1+a[j],a[j])%mod;45 for(j=1;j<i;j++){46 f[i]=(f[i]-f[j]*calc(i,j)%mod+mod)%mod;47 }48 }49 printf("%lld\n",f[n]);50 return 0;51 }52
Bzoj4710 [Jsoi2011]分特产
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。