【bzoj 4710】 [Jsoi2011]分特产

题目

容斥加组合计数

显然答案是

\[\sum_{i=0}^n(-1)^i\binom{n}{i}f_{n-i}
\]

\(f_i\)表示至多有\(i\)个人没有拿到特产

考虑求\(f\)

发现\(m\)种特产每一种是独立的，于是可以考虑对每一种特产分别计算

现在的问题转化成了把\(a_i\)个物品分给\(i\)个人，允许有人没有分到

显然组合数插板

\[f_j=\prod_{i=1}^m\binom{a_i+j-1}{j-1}
\]

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=2e3+1;

const int mod=1e9+7;

inline int read() {

    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

inline LL ksm(LL a,int b) {

    LL S=1;

    while(b) {if(b&1) S=S*a%mod;b>>=1;a=a*a%mod;}

    return S;

}

int n,m;

LL f[maxn],fac[maxn],inv[maxn];

inline LL C(int n,int m) {

    if(m>n) return 0;

    return fac[n]*inv[m]%mod*inv[n-m]%mod;

}

int main() {

    n=read(),m=read();

    fac[0]=1;

    for(re int i=1;i<maxn;i++) fac[i]=(1ll*fac[i-1]*i)%mod;

    inv[maxn-1]=ksm(fac[maxn-1],mod-2);

    for(re int i=maxn-2;i>=0;--i) inv[i]=(1ll*inv[i+1]*(i+1))%mod;

    for(re int i=1;i<=n;i++) f[i]=1;

    for(re int i=1;i<=m;i++) {

        int x=read();

        for(re int j=1;j<=n;j++)

            f[j]=1ll*f[j]*C(x-1+j,j-1)%mod;

    }

    LL ans=0;

    for(re int i=0;i<=n;i++) {

        if(i&1) ans=(ans-f[n-i]*C(n,i)%mod+mod)%mod;

        else ans=(ans+f[n-i]*C(n,i)%mod)%mod;

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

【bzoj 4710】 [Jsoi2011]分特产

最新文章

热门文章