bzoj1042 硬币购物 容斥原理

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1042
Description

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s
i的价值的东西。请问每次有多少种付款方法。
Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000
Output

　　每次的方法数
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27

我们可以看到这道题感觉上有点背包问题的感觉，但是事实上有数据范围可知这是不可能的.当我们看到数据范围很大的时候，我们第一时间要想到数论，因为数学作为一个强有力的工具，能以巧妙的办法化解大数据，比如说这道题所用的容斥原理.

假设每种硬币有无限的数量，那么我们很快就能算出用这四种硬币凑出来面值为i的方案数量f[i].但是题目又要数量限制，这就有很多超过限制的情况.那么我们将问题转化，我们求出超限制的方案数量即可.怎么快速的求出来呢？若求出第一种硬币超出数量的方案，很可能里面包含了第二种硬币也超出了限制的方案，也可能包含了第三种的、第四种硬币的.解集之间存在交集，我们想到了容斥原理.
我们把总方案数（无论数量的，用f数组保存的），我们一一减去第一种硬币超过限制的，再减去第二种超限制的的，第三种超限制的，第四种超限制的的，再加上这四种硬币两两同时超限制的（详见容斥原理），再减去三三的， 加上四四的.每一种超过限制只需要（d[i]+1）*c[i]的钱，剩下的由其他硬币自由分配即可，方案数——f[s-(d[i]+1)*c[i]];

#include<stdio.h>
int c[5],d[5],T,goal;
long long f[100004],ans;
inline const int read(){
    register int f=1,x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
void dfs(int wh,int k,int sum){
    if(sum<0) return;
    if(wh>4){
       if(k&1) ans-=f[sum];
       else ans+=f[sum];
       return;
    }
    dfs(wh+1,k+1,sum-(d[wh]+1)*c[wh]);
    dfs(wh+1,k,sum);
}
int main(){
    for(int i=1;i<=4;i++) c[i]=read();
    f[0]=1;
    for(int i=1;i<=4;i++)
     for(int j=c[i];j<=100000;j++)
      f[j]+=f[j-c[i]];
    T=read();
    while(T--){
      ans=0;
      for(int i=1;i<=4;i++) d[i]=read();
      goal=read();
      dfs(1,0,goal);
      printf("%lld\n",ans);
    }
}