BZOJ4710 【Jsoi2011】分特产

题目链接

Solution

考虑$f[x]$表示不考虑每个人都必须分到土特产的情况下的答案，可以先每个人每种都分一个，然后用挡板来隔来转移。即$f[i][j]=f[i-1][j]*C_{a[i]+j-1}^{j-1}$。容斥一下，显然答案$g[x]=f[x]-\sum_{i=1}^{x-1}g[i]$。

Hints

无

Code

 
​x
#include<bits/stdc++.h>
#define FIO "local_specialty"
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
​
const int maxn=1010;
const int mod=1e9+7;
int n,m,a[maxn],fac[maxn<<1],inv[maxn<<1];
ll g[maxn],f[maxn][maxn]; 
​
inline int C(int x,int y)
{
    if(y>x) return 0;
    if(x>=mod) x%=mod;
    return 1LL*fac[x]*inv[x-y]%mod*inv[y]%mod;
}
​
int main()
{
#ifdef dxymaster
    freopen(FIO".in","r",stdin);
    freopen(FIO".out","w",stdout);
#endif
​
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        a[i]=read();
    fac[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=2001;i++)
        fac[i]=1LL*fac[i-1]*i%mod;
    for(int i=2;i<=2001;i++)
        inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=2001;i++)
        inv[i]=1LL*inv[i]*inv[i-1]%mod;
    for(int i=1;i<=n;i++) f[0][i]=1;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=m;i++)
            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<i;j++)
            g[i]=(g[i]-g[j]*C(i,j)%mod+mod)%mod;
    }
    
    cout << g[n] << endl;
​
#ifdef dxymaster
    cerr<< " Time: " << (double) clock() / CLOCKS_PER_SEC << "s         It Runs So Fast!" << endl;
#endif
​
    return 0;
}