题解 P5505 【[JSOI2011]分特产】

· · 题解

## 题意(简化版本) 有$n$个有标号的盒子和$m$种有标号的球，每种球有$a[i]$个，求每个盒子至少放一种球的总方案数。 ## 分析 直接求合法方案数好像比较复杂，不如我们考虑补集转换？ 总方案数（每个盒子可以为空）-不合法方案数=合法方案数（没有盒子为空） 根据简化后的题意，很自然地想到$TwelveFoldWay$，我们可以先考虑每一种$a[i]$的情况，也就是把$a[i]$个无标号的球放在$n$个有标号的盒子里，允许有空盒，也就是经典的$ULB$问题，方案数就应该是$C(n+a[i]-1,n-1)$，根据乘法原理，所以最后$m$种球的总方案就应该是$\prod_{i=1}^{m}C(n+a[i]-1,n-1)$。 那么现在考虑不合法方案数，如果总方案数中是可以有空的盒子，那么我们的不合法方案数就可以是：一个盒子为空，两个盒子为空...一直到有$n-1$个盒子为空的情况。 假设现在我们在求有$x$个盒子为空的情况，就相当于把$a[i]$个球放进了$n-x$个盒子当中，方案数$C(n-x+a[i]-1,n-x-1)$，根据乘法原理，有i个盒子为空对答案的贡献就应该是$\prod_{j=1}^{m}C(n-i+a[j]-1,n-i-1)$，又考虑到盒子是有标号的，我们选择不同的盒子为空，方案数也不同，于是就要在方案数基础上$*$一个$C(n,i)$，那么，有i个盒子为空的总贡献就应该是 $C(n,i)*\prod_{j=1}^{m}C(n-i+a[j]-1,n-i-1)

已经到了这一步，相信大家就已经看出来接下来就是一个容斥了，那么最终的通式就应该是：

\sum_{i=0}^{n-1}(-1)^iC(n,i)\prod_{j=1}^{m}C(n+a[j]-i-1,n-i-1)

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
const int mod=1e9+7;
int c[2005][2005],n,m,a[2005];
int pow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a*a%mod;
        b>>=1;
    }
    return ans;
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<=2000;i++)
    c[i][i]=c[i][0]=1;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    int ans=0;
    for(int i=0;i<=n-1;i++)
    {
        int cnt=1;
        for(int j=1;j<=m;j++)
        cnt=cnt*c[n+a[j]-i-1][n-i-1]%mod,cnt%=mod;
        if(i%2)ans=(ans-cnt*c[n][i]%mod+mod)%mod;
        else ans=(ans+cnt*c[n][i]%mod)%mod;
    }
    printf("%d\n",ans);
    return 0;   
}