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

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

每次的方法数

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

4
27

题目分析：

这道题没有多组数据用分组背包就可搞，然而多组数据TLE->正解竟然用容斥原理.....

先用完全背包把不受限制的方案数都拿出来 然后再减去受限的方案数 具体怎么减，用容斥原理。

这里是有关容斥原理(+错排公式)的讲解(4集合的容斥原理公式)

抢个图：

也就是说：假设上图整个平面是不受限的方案数 那么我们需要圈内的东西减掉，并只能减去一次

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long f[101000];
int c[10],s,t;
int d[10];
long long n(int x)
{
	return x<0?0:f[x];
}
int main()
{
	f[0]=1;
	scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&t);
	for(int i=1;i<=4;i++)
		for(int j=1;j<=100000;j++)
			if(j>=c[i]) f[j]+=f[j-c[i]];
    for(;t;t--)
    {
    	for(int i=1;i<=4;i++) scanf("%d",&d[i]);
    	scanf("%d",&s);
    	long long ans=f[s];
    	for(int i=1;i<=4;i++)
    		ans-=n(s-c[i]*(d[i]+1));
    	for(int i=1;i<=4;i++)
    		for(int j=i+1;j<=4;j++)
    			ans+=n(s-c[i]*(d[i]+1)-c[j]*(d[j]+1));
    	for(int i=1;i<=4;i++)
    		for(int j=i+1;j<=4;j++)
    			for(int k=j+1;k<=4;k++)
    				ans-=n(s-c[i]*(d[i]+1)-c[j]*(d[j]+1)-c[k]*(d[k]+1));
    	ans+=n(s-c[1]*(d[1]+1)-c[2]*(d[2]+1)-c[3]*(d[3]+1)-c[4]*(d[4]+1));
    	printf("%lld\n",ans);
    }
    return 0;
}