bzoj4710 [Jsoi2011]分特产（容斥）

2023-08-13 16:24:28

4710: [Jsoi2011]分特产

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 814 Solved: 527
[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

如果不保证每个同学都分到特产，那就比较好算

对于每种特产的数量$A_i$，我们求把它分成$n$个非负整数的方案数

先假装给每个非负整数+1，问题转化为把$A_i+n$分成$n$个正整数的方案数

用上熟悉的插板法，$A_i+n-1$个空，一个空最多插一次板，共插$n-1$次板，答案即为$C(A_i+n-1,n-1)$

蓝后考虑减去有同学没拿到特产的方案数

显然要用上熟悉的容斥原理辣：减去1个同学没拿到的方案，加上2个同学没拿到的方案，.........

于是最终$ans=\sum_{i=0}^{n}\; (-1)^i*C(n,i)*\; \prod_{j=1}^{m}\; C(A_i+n-j-1,n-j-1)$

#include<iostream>

#include<cstdio>

#include<cstring>

#define rint register int

using namespace std;

typedef long long ll;

#define N 2005

const ll P=1e9+;

inline ll Md(ll a){return a<P?a:a-P;}

int n,m;ll C[N][N],ans,A[N];

void prep(){

    C[][]=;

    for(rint i=;i<N;++i){

        C[i][]=;

        for(rint j=;j<=i;++j)

            C[i][j]=Md(C[i-][j]+C[i-][j-]);

    }

}

ll F(int x){

    if(x==) return ;//注意边界

    ll re=;

    for(rint i=;i<=m;++i) re=re*C[A[i]+x-][x-]%P;

    return re;

}

int main(){

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

    for(rint i=;i<=m;++i) scanf("%lld",&A[i]);

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

        ans=Md((ans+1ll*((i&)?-:)*C[n][i]*F(n-i))%P+P);

    printf("%lld",ans);

    return ;

}

码农公寓