题解 P5505 【[JSOI2011]分特产】

· · 题解

容斥原理

解决方案

看了一下这道题的题解，我觉得没有人阐释清楚在容斥的时候为什么会出现一加一减的情况，所以自己附上一篇题解

我们设g[i]表示刚好有i个同学没有土特产，由于每个同学都至少要获得一个土特产，那么显然g[0]即为我们的答案。

接下来我们考虑如何求解g[0]

设f[i]表示至少有i个同学没有土特产，要想求解g[0]，我们得先解决f数组

求解f数组

我们可以根据f[i]的定义，强制规定有i个同学没有土特产，然后我们就能通过隔板法求得剩下的同学分特产的方案数。这里再仔细说明一下，f[i]表示的是至少有i个同学没有土特产，所以我们强制规定的作用就在于维护f数组的这个性质，又因为至少，所以我们不用保证剩下的同学每个人必须有特产，不了解隔板法的同学可以自己去百度上搜索一下，这里我便不再仔细阐述，单走一个在可以为空的情况下隔板的公式，既是将m个东西随意分给n个人的方案数为

C_{m+n-1}^{n-1}

然后我们分别处理每个特产分出去的方案数，最后的乘积就是答案。然后由于强制哪个同学也不确定，而规定i个同学不能选到的方案数其实就是从n个人里面选出i个人的组合数，即为

C_n^i

所以，综上所述

f[i]=C_n^i\times\prod_j^mC_{a[j]+n-i-1}^{n-i-1}

解释一下减去i的原因，i为强制没有特产的人数，所以后面分特产的人数就要减去i。

为什么最后的答案为ans=\sum_{i=0}^{n-1} (-1)^if[i]

其实我们可以发现，例如计算至少有一个人没有分到的方案数时，假设我们在规定x不能选到时，处理将特产分给剩下的n-1个人的时候，可能会出现有人分不到特产的情况，我们有一种情况刚好是y没有分到特产，那么在规定y不能选到时，我们也能找到x分不到特产的情况，我们忽略当规定某个人不能分到且另一个人刚好也没有分到的情况时其他人分到特产情况的方案数，原因是我们可以发现，对于x和y来说，当他们找到对方时，其他人分到特产的方案数是不变的。所以我们可以默认在f[1]中，g[2]是被计算了两次的，因为在规定x不分到特产的情况下会出现y分不到特产的情况，但在y规定分不到特产时也会出现x分不到特产的情况，所以说g[2]被计算了两次，我们以样例为例，可以发现

f[0]=g[0]+g[1]+g[2]+g[3]+g[4] f[1]=g[1]+g[2]*2+g[3]*3+g[4]*4 f[2]=g[2]+g[3]*3+g[4]*6 f[3]=g[3]+g[4]*4 f[4]=g[4]

我们可以发现，通过上述的ans公式计算，答案刚好为g[0]，多试几次后发现这个规律具有普遍性，所以

ans=\sum_{i=0}^{n-1} (-1)^iC_n^i\times\prod_j^mC_{a[j]+n-i-1}^{n-i-1}

即为我们的答案，附上AC代码

code

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int N=2010,MOD=1000000007;
typedef long long ll;
int n,m;
ll ans,a[N],c[N][N];    

inline void intial()    //初始化组合数 
{
    c[0][0]=1;
    for(int i=1;i<=N-5;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
    }
}

int main()
{
    intial();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)    
        scanf("%lld",&a[i]);
    //设数组g[i]表示 刚好 有i个同学没有土特产，显然g[0]就是答案
    //设f[i]表示 至少 有i个同学没有土特产，通过计算发现每个f[i]可能会重复计算g[i]，以样例为例 
    //f[0]=g[0]+g[1]+g[2]+g[3]+g[4]
    //f[1]=g[1]+g[2]*2+g[3]*3+g[4]*4
    //f[2]=g[2]+g[3]*3+g[4]*6
    //f[3]=g[3]+g[4]*4
    //f[4]=g[4]
    //根据容斥原理得到公式： 
    //ans=f[0] -f[1]+f[2]-f[3]+...+(-1)(n次方)f[n] 
    for(int i=0;i<n;i++){        //强制任一i个同学没有特产，那么有c[n][i]种方法 
        ll res=c[n][i];             //隔板法，再通过可重复组合计算易得： 
        for(int j=1;j<=m;j++)        //m个东西随意分给n个人方案数为c[m+n-1][n-i-1],一共的方案数就要把这些土特产的方案数全部乘起来 
            res=res*c[a[j]+n-i-1][n-i-1]%MOD;
        if(i&1) ans=(ans-res+MOD)%MOD;      //求得f[i]后根据ans公式即可求解 
        else ans=(ans+res+MOD)%MOD; 
    }
    printf("%d\n",ans); 
    return 0;
}