讲真的看到题,我都没想容斥原理...是我太菜了吗.
首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.
假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...
其实假设我们只能取d[i]个了,这个面值是c[i],我们假定选出来d[i]+1个.那么剩下的空间随便取,然后都是不合法的了,所以合法的就是种数就确定了

dp[n-(d[i]+1)*c[i]].

同理哈,两个不合法就是

dp[n-(d[i]+1)*c[i]-(d[j]+1)*c[j]].

三个四个同理.
但是一个不合法中又可能包含两个不合法的情况,这时候就是容斥原理了,ans=0-1+2-3+4..?
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5,M=1e5+5;
int c[N],d[N];ll f[M],ans;
int main()
{
    int m=4,T,n;
    for(int i=1;i<=m;i++)    scanf("%d",&c[i]);
    scanf("%d",&T);
    f[0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=c[i];j<=M-5;j++)
        {
            f[j]+=f[j-c[i]];
        }
    }//完全背包预处理.
    while(T--)
    {
        ans=0;
        for(int i=1;i<=m;i++)    scanf("%d",&d[i]);
        scanf("%d",&n);
        for(int i=0;i<(1<<4);i++)//容斥原理.0表示不取,1表示取.
        {
            int num=0,t=n;//统计下1的个数是奇数(+)还是偶数(-)
            for(int j=1;j<=4;j++)
            {
                if(i>>(j-1)&1)    t-=(d[j]+1)*c[j],num++;
            }
            if(t<0)    continue;
            if(num&1)   ans-=f[t];
            else        ans+=f[t];
        }
        printf("%lld\n",ans);
    }
    return 0;
}
//不会容斥原理的萌新.