[BZOJ3027][Ceoi2004]Sweet 容斥+组合数

时间:2021-03-01 17:15:32

3027: [Ceoi2004]Sweet

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 135  Solved: 66
[Submit][Status][Discuss]

Description

John得到了n罐糖果。不同的糖果罐,糖果的种类不同(即同一个糖果罐里的糖果种类是相同的,不同的糖果罐里的糖果的种类是不同的)。第i个糖果罐里有 mi个糖果。John决定吃掉一些糖果,他想吃掉至少a个糖果,但不超过b个。问题是John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢?

Input

从标准输入读入每罐糖果的数量,整数a到b 
 
John能够选择的吃掉糖果的方法数(满足以上条件)

Output

把结果输出到标准输出(把答案模 2004 输出)

1<=N<=10,0<=a<=b<=10^7,0<=Mi<=10^6

Sample Input

2 1 3
3
5

Sample Output

9

HINT

(1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1)

Source

对糖果是否装满容斥,通过插板法计算方案。

模数不为质数但n很小,可以将模数乘n!之后除n!。

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
LL n,a,b;
LL m[];
LL mod=,mul=;
LL c(LL x,LL y) {
if(x<y) return ;
LL ans=;
for(int i=x;i>=x-y+;i--) ans=1LL*ans*i%mod;
return (ans/mul)%2004LL;
}
LL cnt(LL x) {
LL ans=;
for(int i=;i<(<<n);i++) {
LL f=,s=x;
for(int j=;j<=n;j++) if((<<(j-))&i) f++,s-=m[j]+;
if(s<) continue;
if(f&) ans-=c(s+n,n);
else ans+=c(s+n,n);
ans%=2004LL;
}
return ans;
}
int main() {
scanf("%lld%lld%lld",&n,&a,&b);
for(int i=;i<=n;i++) scanf("%lld",&m[i]);
for(int i=;i<=n;i++) mod*=i,mul*=i;
printf("%lld",((cnt(b)-cnt(a-))%2004LL+2004LL)%2004LL);
}