题面
有 (n) 个不同的盒子和 (m) 种不同的球，第 (i) 种球有 (a_i) 个，用光所有球，求使每个盒子不空的方案数。
数据范围：(1le n,m,a_ile 1000)。
蒟蒻语
今天做了几道黑题，蒟蒻的做法非常蒟蒻，看上去很厉害其实很废，巨佬的做法是容斥，秒杀一切。
所以蒟蒻拿这道水题讲讲自己的做法。希望巨佬教蒟蒻容斥 ( t /kel)。
蒟蒻解
看到盒子不能空，先二项式反演。
(f(i)) 表示 (i) 个盒子空，剩下非空的方案数；(g(i)) 表示 (i) 个盒子空，剩下随意。
[g(i)=sum_{x=i}^n {xchoose i}f(x)Longleftrightarrow f(i)=sum_{x=i}^n{xchoose i}(-1)^{x-i}g(x)
]
然后考虑 (g(i)) 怎么求：因为 (n-i) 个可以空可以不空，所以可以构造生成函数：
[left(prod_{j=1}^m(1+x_j+x_j^2+x_j^3+cdots)
ight)^{n-i}
]
(g(i)) 就等于 (prod_{j=1}^mx_j^{a_j}) 的项数。
所以可以每个 (x_j) 分开来考虑，用隔板法，得出：
[g(i)={nchoose i}prod_{j=1}^m{a_j+n-i-1choose n-i-1}
]
然后答案就是（当 (x=n) 时 (n-x-1=-1)，所以结果为 (0)，不需要枚举）：
[f(0)=sum_{x=0}^{n-1}(-1)^{x}{nchoose x}prod_{j=1}^m{a_j+n-x-1choose n-x-1}
]
代码
跟巨佬的代码是一样的，只不过推导过程不同。
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define be(a) a.begin()
#define en(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e3,T=N<<1;
const int mod=1e9+7;
int n,m,a[N],c[T+1][T+1];
int g(int x){
int res=c[n][x];
for(int i=0;i<m;i++)
res=(ll)res*c[a[i]+n-x-1][n-x-1]%mod;
return res;
}
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<=T;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<=i-1;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
for(int i=0;i<m;i++) cin>>a[i];
int ans=0;
for(int i=0;i<n;i++){
if(i&1) (ans+=mod-g(i))%=mod;
else (ans+=g(i))%=mod;
}
cout<<ans<<'
';
return 0;
}
祝大家学习愉快！