4710 [Jsoi2011]分特产

题意

给定\(n\)个集合，每个集合有相同的\(a_i\)个元素，不同的集合的元素不同。将所有的元素分给\(m\)个不同位置，要求每个位置至少有一个元素，求分配方案数。

先考虑两个简单的问题

给定\(m\)个相同元素和\(n\)个不同位置，每个位置至少分一个的方案数？

使用插板法，等价于在\(m-1\)个空挡里插\(n-1\)个元素，方案数为

\[\binom{m-1}{n-1}
\]

但是这样考虑，这个题目是做不了的。

给定\(m\)个相同元素和\(n\)个不同位置，每个位置可以不分的方案数？

事实上还是插板，但可以一个位置插两个板子。

把\(m\)个元素看做\(1\)，把\(n-1\)个插开点看做\(0\)，等价于从\(m+n-1\)个元素拿\(n-1\)个，方案数为

\[\binom{m+n-1}{n-1}
\]

从问题\(2\)出发，我们就可以容斥了

把一种方案有几个位置没选作为方案的性质，我们可以计算出一个至少有几个人没选的方案集合的数量。

因为位置的计算方法是等价的，所以我们不需要枚举子集，只需要简单的按照组合数进行计算就可以了。

具体的说，我们把所有集合的元素都独立按方案二的选出来，令\(f_i\)代表至少\(i\)个位置不选择元素的方案数，则有

\[f_i=\binom{n}{i}\prod\limits_{j=1}^n \binom{a_j+n-i-1}{n-i-1}
\]

则总方案是至少\(0\)人-至少\(1\)人+...，即

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

Code:

#include <cstdio>

#define ll long long

const int N=2000;

const ll mod=1e9+7;

ll C[N+10][N+10];

void init()

{

    C[0][0]=1;

    for(int i=1;i<=N;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 n,m,a[N];ll ans;

int main()

{

    init();

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++) scanf("%d",a+i);

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

    {

        ll mu=1;

        for(int j=1;j<=m;j++)

            (mu*=C[a[j]+n-i-1][n-i-1])%=mod;

        (ans+=(i&1?-1ll:1ll)*C[n][i]*mu%mod)%=mod;

    }

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

    return 0;

}

2018.10.18

巴特西

BZOJ 4710 [Jsoi2011]分特产解题报告

4710 [Jsoi2011]分特产

题意

最新文章

热门文章

巴特西

BZOJ 4710 [Jsoi2011]分特产 解题报告

4710 [Jsoi2011]分特产

题意

最新文章

热门文章

BZOJ 4710 [Jsoi2011]分特产解题报告