答案=总方案数-不合法方案数

f[i][j] 前i种特产分给j个人（可能有人没有分到特产）的总方案数

考虑第i种特产的分配f[i][j]=f[i-1][j]*C(a[i]+j-1 , j-1)

g[i] 表示有i个人，每个人至少分到一种特产，其他人都没有分到的方案数

g[i]=f[m][i]-Σg[j]*C(i,j)   j∈[1,i-1]

即有i个人分到特产=总方案数-只有1个人分到特产-只有2个人分到特产……-只有i-1个人分到特产

 

#include
     
      #include
      
       #define N 1001using namespace std;const int mod=1e9+7;int f[N][N],g[N];int a[N];int C[N<<1][N<<1];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int main(){    int n,m;    read(n); read(m);    for(int i=1;i<=m;++i) read(a[i]);    C[0][0]=1;    int mm=1000+n;    for(int i=1;i<=mm;++i)    {        C[i][0]=1;        for(int j=1;j<=i;++j)            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;    }    for(int i=1;i<=n;++i) f[0][i]=1;    for(int i=1;i<=m;++i)        for(int j=1;j<=n;++j)            f[i][j]=1LL*f[i-1][j]*C[a[i]+j-1][j-1]%mod;    for(int i=1;i<=n;++i)    {        g[i]=f[m][i];        for(int j=1;j