Description
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
Input
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
Output
每次的方法数
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27
HINT
数据规模
di,s<=100000
tot<=1000
题解
感觉自己容斥原理根本不会……所以找道题做做。
正解完全背包+容斥。
首先完全背包可以让我们得到四种硬币数量不限时，组成s的方案。但我们要的是四种硬币均满足限制。
设
某种或某几种硬币满足限制的方案数为集合Xi，则我们要求的为X1∩
X2∩……
∩
Xn，我们已知总集合N满足| N |=f[m]。
以下摘自http://www.verydemo.com/demo_c92_i266806.html
接着我们来理解x=f[s]-f[s-(d1+1)*c1]的含义：x表示c1硬币的数量不超过d1个而其他三种硬币的数量不限制拼成s的方案数。我们举着例子来说明，假设现在有两种硬币，面值分别为1和2，那么我们求出f:f[0]=1,f[1]=1,f[2]=2,f[3]=2,f[4]=3,f[5]=3,f[6]=4。其中f[3]的两种分别为3=1+1+1=1+2,f[6]的四种为:6=1+1+1+1+1+1=1+1+1+1+2=1+1+2+2=2+2+2。加入我们现在求第一种硬币最多使用两个，第二种硬币无限制的方案数，按照我们说的x=f[6]-f[6–(2+1)*1]=f[6]-f[3]=2。也就是6=1+1+2+2=2+2+2两种。我们发现我们删除了1+1+1+1+1+1和1+1+1+1+2两种，为什么能够通过减去f[3]删掉这两种？我们来看f[3]，3=1+1+1=1+2，我们发现6中被删掉的两种正是通过这个f[3]增加3个1得到的。
若我们用一个4位的二进制表示状态的话，每位上为1表示第i种
硬币
的数量满足不超过di的限制，0表示无限制，那么我们就是要得到1111，而我们求出的f[s]其实是0000,那么我们怎么由0000得到1111呢？容斥原理：1111=0000-(1000+0100+0010+0001)+(1100+1010+1001+0110+0101+0011)-(1110+1101+1011+0111)+(1111)。
PS：根据以下式子：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int c[4],n,s[4],m;
ll f[100002],ans;
void dp()
{
f[0]=1;
int i,j;
for(j=0;j<4;j++)
for(i=c[j];i<=100000;i++)
f[i]+=f[i-c[j]];
}
void dfs(int w,int num,int k)
{
if(num<0) return;
if(w==4)
{if(k) ans-=f[num];
else ans+=f[num];
return ;
}
dfs(w+1,num,k);
dfs(w+1,num-c[w]*(s[w]+1),k^1);
}
int main()
{
scanf("%d%d%d%d",&c[0],&c[1],&c[2],&c[3]);
scanf("%d",&n);
dp();
int i;
for(i=1;i<=n;i++)
{scanf("%d%d%d%d",&s[0],&s[1],&s[2],&s[3]);
scanf("%d",&m); ans=0;
dfs(0,m,0);
printf("%lld\n",ans);
}
return 0;
}