bzoj 3027: [Ceoi2004]Sweet
一道题含了好多知识点。。
首先母函数不多说看式子。
π(1+x+x^1+x^2+...+x^mi)=π{[1-x^(mi+1)]/[1-x]}=(1-x)^(-n) * π(1-x^(mi+1))=(1+x+x^2+...+x^inf..)^n * π(1-x^(mi+1));
然后答案是f(b)-f(a-1) ,f(m) 表示0到m的系数和
那么后面的π(1-x^(mi+1))可以暴力拆出来，最多2^n项，
然后枚举每一项，枚举到 ax^b, 这项 对f(m)的贡献就是(1+x+x^2+...+x^inf..)^n 的 0~m-b的系数和
即，C(0+n-1,n-1)+C(n,n-1)+C(n+1,n-1)+...+C(m-b+n-1,n-1)，
然后因为C(i,i)+C(i+1,i)+...+C(k,i)=C(k+1,i+1)；(杨辉三角) 那么上式就可以直接化成一个组合数
C(x,y)%2004 怎么求？
其实问题在于，给定x,y ，x是y的倍数，x很大，y比较小。求(x/y)%p (p也挺小的，但不一定和y互质)
设z=x/y ; 求出k=x%(py) → x=k+tpy; 因为y整除x,so y整除k, 且我们求出来的k是%py下的 ，gcd(py,y)==y; 所以最后%意义下的k依然是被y整除的。
k/y%p就是最后的 (x/y)%p
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mo=2004; 4 int n,m,L,R,k,t,w[15]; 5 struct term{ 6 int a,b; 7 }a[2000],b[2000]; 8 bool cmp(term a,term b){ return a.b<b.b; } 9 int gcd(int x,int y){ 10 return y?gcd(y,x%y):x; 11 } 12 int C(int x,int y){ 13 if (x<y) return 0; int z=1,d,u; 14 for (int i=2;i<=n;++i) w[i]=i; 15 for (int i=x-y+1;i<=x;++i){ //我用的不是上面那种求法 16 u=i; 17 for (int j=2;j<=n;++j) if (w[j]>1) d=gcd(u,w[j]),u/=d,w[j]/=d; 18 (z*=u%mo)%=mo; 19 } 20 return z; 21 } 22 int get(int m){ 23 int ans=0; 24 for (int i=1;i<=t;++i){ 25 ans+=C(m-a[i].b+n,n)*a[i].a%mo; 26 if (ans>=mo) ans-=mo; 27 } 28 return ans; 29 } 30 int main(){ 31 scanf("%d%d%d",&n,&L,&R); a[t=1]={1,0}; b[0].b=-1; 32 for (int i=1;i<=n;++i){ 33 scanf("%d",&m); k=0; 34 for (int i=1;i<=t;++i) b[i]=a[i]; 35 for (int i=1;i<=t;++i) b[i+t]={a[i].a?mo-a[i].a:0,m+1+a[i].b}; 36 sort(b+1,b+t+t+1,cmp); 37 for (int i=1;i<=t+t;++i){ 38 if (b[i].b>R) break; 39 if (b[i].b!=b[i-1].b) a[++k]={0,b[i].b}; 40 a[k].a+=b[i].a; if (a[k].a>=mo) a[k].a-=mo; 41 } 42 t=k; 43 } 44 printf("%d",(get(R)-get(L-1)+mo)%mo); 45 return 0; 46 }