【BZOJ 3027】 3027: [Ceoi2004]Sweet （容斥原理+组合计数）

3027: [Ceoi2004]Sweet

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 71 Solved: 34

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

【分析】

　　就是分成（<=b） - (<= a-1）的。

　　然后每个糖果罐容斥，枚举哪些超过了的。

　　假设减掉之后剩下最多选x个糖果

　　就是$C_{0+n-1}^{n-1}+C_{1+n-1}^{n-1}+C_{2+n-1}^{n-1}+...+C_{x+n-1}^{n-1}$

　　求和之后就是$C_{x+n}^{n}$

　　但是！！！模数可能没有逆元，又不能n^2预处理。。

　　【怎么办呢？？？

　　【又涨姿势。。

　　首先都是$C_{x}^{n}$的形式，即$\dfrac{x!}{(x-n )!}/(n!)$

　　n!很小，让$mod=Mod*n!$

　　计算的时候模mod，最后除以n！，再模Mod。。。

　　就可以了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Mod 2004

 #define Maxm 10000010

 #define LL long long

 int w[],n;

 LL mul;

 int get_c(int x,int y)

 {

     if(x<y) return ;

     LL mod=mul*Mod,ans=;

     for(int i=x;i>=x-y+;i--) ans=1LL*ans*i%mod;

     return (ans/mul)%Mod;

 }

 int cal(int x)

 {

     int ans=;

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

     {

         int ss=,sm=x;

         for(int j=;j<=n;j++) if((<<j-)&i)

         {

             ss++;sm-=w[j]+;

         }

         if(sm<) continue;

         if(ss&) ans-=get_c(sm+n,n);

         else ans+=get_c(sm+n,n);

         ans%=Mod;

     }

     return ans;

 }

 int main()

 {

     int a,b;

     scanf("%d%d%d",&n,&a,&b);

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

     for(int i=;i<=n;i++) scanf("%d",&w[i]);

     printf("%d\n",((cal(b)-cal(a-))%Mod+Mod)%Mod);

     return ;

 }

2017-04-25 21:25:39

巴特西

【BZOJ 3027】 3027: [Ceoi2004]Sweet （容斥原理+组合计数）

3027: [Ceoi2004]Sweet

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章