JSOI2011 分特产题解

[JSOI2011]分特产 题目描述

JYY 带队参加了若干场 ACM/ICPC \text{ACM/ICPC} ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。

JYY 想知道，把这些特产分给 n n n 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。

例如，JYY 带来了 2 2 2 袋麻花和 1 1 1 袋包子，分给 A A A 和 B B B 两位同学，那么共有 4 4 4 种不同的
分配方法：

A A A：麻花， B B B：麻花、包子

A A A：麻花、麻花， B B B：包子

A A A：包子， B B B：麻花、麻花

A A A：麻花、包子， B B B：麻花

输入格式

输入数据：

第一行是同学的数量 n n n 和特产的数量 m m m。

第二行包含 M M M 个整数，表示每一种特产的数量。

N , M N,M N,M 不超过 1000 1000 1000 ，每一种特产的数量不超过 1000 1000 1000

输出格式

输出一行，不同分配方案的总数。

由于输出结果可能非常巨大，你只需要输出最终结果
  m o d   1 0 9 + 7 \bmod {10^9+7} mod109+7 的数值就可以了。

样例 #1 样例输入 #1

5 4
1 3 3 5

样例输出 #1

384835

​

题意：

有 n n n个有标号的盒子和 m m m种有标号的球，每种球有 a [ i ] a[i] a[i]个，求每个盒子至少放一种球的总方案数。

分析：

我们可以先考虑–把每个 a [ i ] a[i] a[i]分到 n n n个盒子里（允许有空盒）那么方案数为 C n + a [ i ] − 1 n − 1 \textrm{C}_{n+a[i]-1}^{n-1} Cn+a[i]−1n−1​,

根据乘法原理方案数 ∏ i = 1 m  ⁣ C n + a [ i ] − 1 n − 1 \prod^m_{i=1}\!C^{n-1}_{n+a[i]-1} ∏i=1m​Cn+a[i]−1n−1​ 当然这样想使不完全正确的，其中包含有人没有的情况；

不合法的情况为 K [ i ] K[i] K[i]( i i i表示至少有 i i i个盒子为空）（范围从 i i i到 n − 1 n-1 n−1，上一步求出必有一人有）；

即我们要求出看k[x]= C n + a [ i ] − 1 n − x − 1 \textrm{C}_{n+a[i]-1}^{n-x-1} Cn+a[i]−1n−x−1​（也就是求出将 a [ i ] a[i] a[i]个球放入 n − x n-x n−x个盒子中）；

但是因为 k [ i ]  ⁣ ⊆  ⁣ k [ j ] ( i  ⁣ <  ⁣ j ） k[i]\!\subseteq\! k[j](i\!<\!j） k[i]⊆k[j](i<j）所以容斥一下；

∑ i = 0 n − 1 ( − 1 ) i ∏ j = 1 m C ( n  ⁣ +  ⁣ a [ j ]  ⁣ −  ⁣ i  ⁣ −  ⁣ 1 , n  ⁣ −  ⁣ i  ⁣ −  ⁣ 1  ⁣ ) \boxed{\sum^{n-1}_{i=0}(-1)^i\prod^m_{j=1}C(n\!+\!a[j]\!-\!i\!-\!1,n\!-\!i\!-\!1\!)} i=0∑n−1​(−1)ij=1∏m​C(n+a[j]−i−1,n−i−1)​

#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll n,m,te[1010],C[2010][2010];
int main()
{
    freopen("speciall.in","r",stdin);
    freopen("speciall.out","w",stdout);
    C[0][0]=1;
    for(int i=1;i<=2005;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;
        }
    }//预处理
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&te[i]);
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        ll t=C[n][i];
        for(int j=1;j<=m;j++)
        {
            t=t*C[te[j]+n-i-1][n-i-1]%mod;
        }
        if(i&1) ans=(ans-t+mod)%mod;
        else ans=(ans+mod+t)%mod;
    }
    printf("%lld",(ans+mod)%mod);
}

 //设数组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] 

​