例题一 [JSOI2011]分特产
题目描述
JYY 带队参加了若干场 \(\text{ACM/ICPC}\) 比赛，带回了许多土特产，要分给实验室的同学们。
JYY 想知道，把这些特产分给 \(n\) 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。
例如，JYY 带来了 \(2\) 袋麻花和 \(1\) 袋包子，分给 \(A\) 和 \(B\) 两位同学，那么共有 \(4\) 种不同的
分配方法：
\(A\)：麻花， \(B\)：麻花、包子
\(A\)：麻花、麻花， \(B\)：包子
\(A\)：包子， \(B\)：麻花、麻花
\(A\)：麻花、包子， \(B\)：麻花
思路点拨
我们设 \(f(x)\) 表示至多有 \(x\) 个童鞋获得了特产的方案数。 \(g(x)\) 表示刚好有 \(x\) 个童鞋获得了特产的方案数。那么有
\[f(x)=\sum_{i=0}^x C_{x}^{i}g(i) \]二项式反演可得：
\[g(x)=\sum_{i=0}^x (-1)^{x-i}C_{x}^if(i) \]考虑 \(f(x)\) 的求法。我们一个个枚举每一种特产，然后插板法进行分发特产。因为元素可空，所以 \(m\) 个元素分成 \(n\) 分的方案是 \(C_{n+m-1}^{n-1}\) 。
Q:为什么特产需要一个个枚举而不是可以一起分发？
A:因为在本题中，特产是一样的，如果一起分发会造成答案重复。
\(code\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=2e3+10,N=2e3,mod=1e9+7;
int sum[MAXN]={1},inv[MAXN]={1};
int qpow(int a,int b){
int ans=1,base=a;
while(b){
if(b&1) ans=(ans*base)%mod;
base=(base*base)%mod;
b>>=1;
}
return ans;
}
void prepare(){
sum[0]=inv[0]=1;
for(int i=1;i<=N;i++){
sum[i]=sum[i-1]*i%mod;
inv[i]=qpow(sum[i],mod-2);
}
}
int C(int n,int m){return sum[n]*inv[m]%mod*inv[n-m]%mod;}
int n,m,a[MAXN];
signed main(){
prepare();
n=read(),m=read();
int ans=0;
for(int i=1;i<=m;i++){
a[i]=read();
ans+=a[i];
}
if(ans<n) cout<<0;
else{
ans=0;
for(int i=0;i<=n;i++){
int temp=C(n,i);
for(int j=1;j<=m;j++)
temp=temp*C(i+a[j]-1,i-1)%mod;
if((n-i)&1) ans=(ans-temp+mod)%mod;
else ans=(ans+temp)%mod;
}
cout<<ans;
}
return 0;
}