这个相当神奇,用容斥原理做背包。
首先,我们要先处理出四种钞票都不限的方案数。
对于每一个询问,我们利用容斥原理,答案为:得到S所有超过数量限制的方案数-硬币1超过限制的方案数-硬币2超过限制的方案数-硬币3超过限制的方案数-硬币4超过限制的方案数+硬币1、2超过限制的方案数+…+硬币1、2、3、4均超过限制的方案数。
而对于每种方案数的求法,也非常简单:假设我们要求的是F[S],则硬币1超过限制(即硬币1取的个数≥d[1]+1,不考虑硬币2、3、4是否超过限制)时的方案数即为F[S-(d[1]+1)×c[1]]。
1 /************************************************************** 2 Problem: 1042 3 User: zhuohan123 4 Language: C++ 5 Result: Accepted 6 Time:44 ms 7 Memory:2132 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 #include 14 using namespace std;15 int c[5];16 long long F[110000];17 struct{ long long operator[](int pos){ return pos<0?0:F[pos];}}f;18 int main(int argc, char *argv[])19 {20 int T;scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&T);21 F[0]=1;22 for(int i=1;i<=4;i++)23 for(int j=0;j<=100000;j++)24 if(j+c[i]<=100000)F[j+c[i]]+=F[j];25 while(T--)26 {27 int d[5],s;scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);28 long long ans=f[s];29 ans-=f[s-(d[1]+1)*c[1]];30 ans-=f[s-(d[2]+1)*c[2]];31 ans-=f[s-(d[3]+1)*c[3]];32 ans-=f[s-(d[4]+1)*c[4]];33 ans+=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]];34 ans+=f[s-(d[1]+1)*c[1]-(d[3]+1)*c[3]];35 ans+=f[s-(d[1]+1)*c[1]-(d[4]+1)*c[4]];36 ans+=f[s-(d[2]+1)*c[2]-(d[3]+1)*c[3]];37 ans+=f[s-(d[2]+1)*c[2]-(d[4]+1)*c[4]];38 ans+=f[s-(d[3]+1)*c[3]-(d[4]+1)*c[4]];39 ans-=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]];40 ans-=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[4]+1)*c[4]];41 ans-=f[s-(d[1]+1)*c[1]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];42 ans-=f[s-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];43 ans+=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];44 #ifdef ONLINE_JUDGE45 printf("%lld\n",ans);46 #else47 printf("%I64d\n",ans);48 #endif49 }50 return 0;51 }