Discription
JYY 带队参加了若干场ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。
JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任
何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。
例如，JYY 带来了2 袋麻花和1 袋包子，分给A 和B 两位同学，那么共有4 种不同的
分配方法：
A：麻花，B：麻花、包子
A：麻花、麻花，B：包子
A：包子，B：麻花、麻花
A：麻花、包子，B：麻花
输入数据第一行是同学的数量N 和特产的数量M。
第二行包含M 个整数，表示每一种特产的数量。
N, M 不超过1000，每一种特产的数量不超过1000
输出一行，不同分配方案的总数。由于输出结果可能非常巨大，你只需要输出最终结果
MOD 1,000,000,007 的数值就可以了。
5
4 1 3 3 5
Sample Output
384835
Hint
挺简单的一道组合数学，，，可重集组合水一水就过了23333。
设 g(i) 为 至少有 i个人一个特产都没有得的方案数， 那么 g(i) = C(n,i) * πC(n-i-1+a[j] , a[j]) ，就是考虑哪些人没有选，已经选了的人选的方案。
再设 f(i) 为 有i个人一个特产没得的方案数，可以发现的是 一个 f(i) 会在 一个 g(j) 里被算 C(i,j) 次，所以我们就构造一个容斥系数，
使得 对于我们需要的 i ，Σ x[j] * C(i,j) = 1 ; 而对于其他的 i ，Σ x[j] * C(i,j) = 0。
本题我们需要的仅仅是 f[0]，所以这个系数很好构造，令所有奇数的j的x为-1，偶数的为1就行了，正好这也是我们常见的容斥系数，所以不会构造也能水过本题吧233
#include<bits/stdc++.h>#define ll long longusing namespace std;const int ha=1000000007;const int maxn=2005;using namespace std;int C[maxn][maxn];int n,m,a[maxn];int g[maxn];inline int add(int x,int y){x+=y;return x>=ha?x-ha:x;}inline void init(){C[0][0]=1;for(int i=1;i<=2000;i++){C[i][0]=1;for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j-1],C[i-1][j]);}}inline void solve(){for(int i=0,lef;i<=n;i++){g[i]=C[n][i],lef=n-i-1; ???for(int j=1;j<=m;j++) g[i]=g[i]*(ll)C[a[j]+lef][a[j]]%ha;}int ans=0;for(int i=0;i<=n;i++){if(i&1) ans=add(ans,ha-g[i]);else ans=add(ans,g[i]);}printf("%d\n",ans);}int main(){init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d",a+i);solve();return 0;}
[JSOI2011]分特产
原文地址：https://www.cnblogs.com/JYYHH/p/8548381.html