bzoj4710: [Jsoi2011]分特产 组合+容斥

时间：2023-03-09 06:52:06
bzoj4710: [Jsoi2011]分特产 组合+容斥

4710: [Jsoi2011]分特产

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 289  Solved: 198
[Submit][Status][Discuss]

Description

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

JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任

何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。

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

分配方法：

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

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

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

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

Input

输入数据第一行是同学的数量N 和特产的数量M。

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

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

Output

输出一行，不同分配方案的总数。由于输出结果可能非常巨大，你只需要输出最终结果

MOD 1,000,000,007 的数值就可以了。

Sample Input

5 4
1 3 3 5

Sample Output

384835

容斥+组合
ans=所有分法-至少1个同学没有的分法+至少2个同学没有的分法...
每种特产是独立的，用乘法原理
对于每种特产，考虑用插板原理计算分法即C(n+m-1,m-1)

推荐blog
http://blog.****.net/clove_unique/article/details/64918833

/*

容斥+组合

ans=所有分法-至少1个同学没有的分法+至少2个同学没有的分法...

每种特产是独立的，用乘法原理

对于每种特产，考虑用插板原理计算分法即C(n+m-1,m-1)

推荐blog

http://blog.****.net/clove_unique/article/details/64918833

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 2005

#define mod 1000000007

using namespace std;

int a[N],c[N][N],n,m,ans;

void pre(){

    for(int i=0;i<=2000;i++)c[i][0]=c[i][i]=1;

    for(int i=1;i<=2000;i++)

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

    c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

}

int main(){

#ifdef wsy

    freopen("data.in","r",stdin);

#else

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

#endif

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

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

    scanf("%d",&a[i]);pre();

    ll ans=0;

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

        ll now=1;

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

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

        ans=(ans+now*(i&1?-1:1)*c[n][i])%mod;

    }

    ans<0?ans+=mod:1;

    printf("%lld",ans);

    return 0;

}

相关文章