2017-03-09

【bzoj4710】分特产

不要相信这个调了2个小时的sb

AC通道

我们只需要枚举多少个同学没有分到即可进行容斥

错误记录：

（1）求组合数时没有令c[0][0]=1;
（2）搞错位运算优先级
（3）组合数取模没有加括号

我是不是应该滚去普及组了

#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
const int mod=1e9+7,MAXN=2000,D=50;
int n,m,a[MAXN+D];
ll ans,c[MAXN+D][MAXN+D];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void pre(){
	for(int i=0;i<=MAXN;++i)  c[i][0]=c[i][i]=1LL;
	for(int i=1;i<=MAXN;++i)
		for(int j=1;j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  pre();
	for(int i=1;i<=m;++i)  a[i]=read();
	for(int i=n;i>=0;--i){
		ll f=((i&1)==(n&1)?1:-1);  f=f*c[n][i]%mod; 
		for(ll j=1;j<=m;++j)  f=(f*c[a[j]+i-1][i-1]+mod)%mod;
		ans+=f;  ans=(ans+mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

本文标题:【bzoj4710】分特产

文章作者:chty

发布时间:2017年03月09日 - 16时18分

最后更新:2018年03月02日 - 17时15分

许可协议:本文为博主原创，未经许可不得转载。