试题描述：
现在一共有4种硬币，面值各不相同，分别为ci(i=1,2,3,4)。某人去商店买东西，去了tot次，每次带di枚ci硬币，购买价值为si的货物。请问每次有多少种付款方法。
输入：
第一行包括五个数，分别为c1,c2,c3,c4和tot 接下来有tot行，每行五个数，第i+1行五个数依次为第i次购物所带四种硬币的数目和购买货物的价值（d1,d2,d3,d4,s ）。各行的数两两之间用一个空格分隔。
输出：
tot行，依次为每次付款的方法数。
输入示例：
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
输出示例：
4
27
数据范围：
0<di,s<=100000,0<tot<=1000。
这道题其实就是一个dp+容斥原理(不知道什么是容斥原理的自己上网百度去)……
首先我们先对于dp数组进行初始操作。我们定义：dp[i]是在不考虑硬币是否超限的情况下用硬币凑i元的方案数。这样我们就可以得到状态方程：dp[j]+=dp[j-c[i]](由数据发现我们的0<=j<=100000，1<=i<=4)注意：dp[0]=1
然后我们就可以进行容斥原理的操作。对于每种硬币，都有超和不超两种情况，所以最终我们只需要统计2^4=16次就够了。在记录状态的时候，我们可以用10进制的数来记录，可是在操作的时候其实是对2进制进行操作。举个例子：比如我用5记录了一种状态，5的二进制就是0101，其表达的意思就是第一种和第三种硬币超出了限度。
那么我们应该如何来表示使用硬币超过了限度？举个例子：比如当前第i种硬币有d[i]枚硬币可以用的话，如果我们用到了d[i]+1枚硬币那就是说我们用硬币超过了限度，且其他硬币是可以随意使用的，所以这样的情况应该有dp[s-c[i]*(d[i]+1)]种，如果s-c[i]*(d[i]+1)<0那方案数也就是0。其余的情况也类似。
这题是要开long long的，要不过不去……我就是这么死的……
AC代码：
#include<iostream> #include<memory.h> #include<stdio.h> #include<cstdio> #include<cctype> using namespace std; //-------------------------- void read(long long &x){ x=0;char ch=getchar();long long f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; x*=f; } //--------------------------- long long c[5],d[5],s,tot,ans,cnt,sum,cur; long long dp[100000+10]; bool flag=0; int main(){ for(int i=1;i<=4;i++){ read(c[i]); } read(tot); dp[0]=1; for(int i=1;i<=4;i++){ for(int j=c[i];j<=100000;j++)dp[j]+=dp[j-c[i]]; } while(tot--){ for(int i=1;i<=4;i++)read(d[i]); read(s); ans=0; for(int i=0;i<16;i++){ cnt=0;sum=0;cur=0; int t=i; while(t>0){ cur++; if(t&1)sum+=(d[cur]+1)*c[cur],cnt++; t>>=1; } if(s<sum)continue; if(cnt&1)ans-=dp[s-sum]; else ans+=dp[s-sum]; } printf("%lld ",ans); } }