题目链接：

https://www.lydsy.com/JudgeOnline/problem.php?id=4710

题意：m种物品，每种 $a_i </annotation> </semantics> </math>$

如果就只有一种土特产的话就是灰常标准的隔板法了，但是现在是m种怎么办呢？
直接来凑就要这种分给那几个人，下一种又分给那些还没得到的人。。。。这样凑要凑成最后每个人都至少分到一个。如果没有每人至少一个的条件，又比较好办，那就直接每种特产拿去分，用至少0个那种隔板法，然后把每次的分的方法数乘起来就行了。

但现在就是加了这个每人至少一个的条件怎么办呢？

又是容斥。。。
枚举多少个人没有分到，奇数个人没有分到就减，偶数个就加
为啥这样就阔以了喃？感觉不能完全理解啊

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n||n<0?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int N,M;
int a[maxn];
LL ksm(LL a,LL b,LL mod)
{
	LL res=1,base=a;
	while(b)
	{
		if(b&1)res=(res*base)%mod;
		base=(base*base)%mod;
		b>>=1;
	}
	return res;
}
LL fac[maxn]={1,1},invf[maxn]={1,1};
void InitFac(int n)
{
	for(int i=2; i<=n; i++)fac[i]=fac[i-1]*i%MOD;
	invf[n]=ksm(fac[n],MOD-2,MOD);
	for(int i=n-1; i>=2; i--)invf[i]= invf[i+1]*(i+1)%MOD;
}
LL geban0(int n,int x)//隔板法x个物品分给n个人，每人至少0个 
{
	return C(x-1+n,n-1);
}

LL given(int n)//m种特产分别分给n个人，用乘法 
{
	LL res=1;
	for(int i=1;i<=M;i++)res=res*geban0(n,a[i])%MOD;
	return res;
}

int main()
{
	InitFac(maxn-5);
	while(cin>>N>>M)
	{
		for(int i=1;i<=M;i++)cin>>a[i];
		LL res=0;
		for(int i=0;i<=N;i++)//i个人没有分到 
		{
			LL tp=C(N,i)*given(N-i);
			if(i%2)res-=tp;
			else res+=tp;
			res%=MOD;
		}
		res=(res+MOD)%MOD;
		cout<<res<<endl;
	}
}

bzoj 4710 分特产

文章目录

题目链接：