题目描述
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
输入输出格式
输入格式：
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
输出格式：
每次的方法数
输入输出样例
输入样例#1：
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
输出样例#1：
4
27
说明
di,s<=100000
tot<=1000
[HAOI2008]
这道题是道数论题 首先我们可以没有限制地像完全背包一样求出f【i】
f【i】表示硬币合起来是 i 的方案数
然后利用容斥原理 用总的方案数减去不合法的方案数就好啦
用递归实现代码比较简洁
类似于
总的方案数 -一种超的方案数和+两种超的方案数和-三种超的方案数和~~~~~~~~~
具体的容斥原理百度学学咯？
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL read(){
LL ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL s,c[],d[],T;
LL ans,f[];
void rc(int i,int s,int k){
if(i==){
ans+=f[s]*k;
return ;
}
rc(i+,s,k);
if((LL)c[i]*(d[i]+)<=s) rc(i+,s-(c[i]*(d[i]+)),-k);
}
int main()
{
c[]=read(); c[]=read(); c[]=read(); c[]=read();
T=read(); f[]=;
for(int i=;i<=;i++)
for(int j=c[i];j<=;j++)
f[j]+=f[j-c[i]];
while(T--){
d[]=read(); d[]=read(); d[]=read(); d[]=read(); s=read();
ans=; rc(,s,);
printf("%lld\n",ans);
}
return ;
}