试题描述：
现在一共有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=;char ch=getchar();long long f=;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';
x*=f;
}
//---------------------------
long long c[],d[],s,tot,ans,cnt,sum,cur;
long long dp[+];
bool flag=;
int main(){
for(int i=;i<=;i++){
read(c[i]);
}
read(tot);
dp[]=;
for(int i=;i<=;i++){
for(int j=c[i];j<=;j++)dp[j]+=dp[j-c[i]];
}
while(tot--){
for(int i=;i<=;i++)read(d[i]);
read(s);
ans=;
for(int i=;i<;i++){
cnt=;sum=;cur=;
int t=i;
while(t>){
cur++;
if(t&)sum+=(d[cur]+)*c[cur],cnt++;
t>>=;
}
if(s<sum)continue;
if(cnt&)ans-=dp[s-sum];
else ans+=dp[s-sum];
}
printf("%lld\n",ans);
}
}