吐槽

看完题之后的心理反应:
这这?不是一个数学小蓝皮上母函数的模板题吗
想了一会儿,发现还是WTCL

分析

一道简单的容斥DP题
我们发现
我们先考虑一下弱化版本
如果每个硬币都不受限
那么我们就可以直接暴力背包求得所有方案书

所以我们现在来考虑一下本题
发现,我们可以容斥解决
先把答案设为DP[Cost]
然后减去有一个超过限制时的方案数
加上两个超过限制的方案数

当然,前提是可以超过限制
时间复杂度:

代码

//P1450
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=1e5+10;

LL DP[MaxN]={1};
LL Cost[5],Cnt[5];
LL Test,Sum,Ans;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline LL Calc(LL New) { return Cost[New]*(Cnt[New]+1); }

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Cost[1]>>Cost[2]>>Cost[3]>>Cost[4]>>Test;
    FOR(i,1,4) FOR(j,Cost[i],1e5) { DP[j]+=DP[j-Cost[i]]; }
    while(Test--) {
        Ans=0;
        cin>>Cnt[1]>>Cnt[2]>>Cnt[3]>>Cnt[4]>>Sum;
        Ans=DP[Sum];
        if(Sum>=Calc(1)) Ans-=DP[Sum-Calc(1)];
        if(Sum>=Calc(2)) Ans-=DP[Sum-Calc(2)];
        if(Sum>=Calc(3)) Ans-=DP[Sum-Calc(3)];
        if(Sum>=Calc(4)) Ans-=DP[Sum-Calc(4)];
        if(Sum>=Calc(1)+Calc(2)) Ans+=DP[Sum-Calc(1)-Calc(2)];
        if(Sum>=Calc(1)+Calc(3)) Ans+=DP[Sum-Calc(1)-Calc(3)];
        if(Sum>=Calc(1)+Calc(4)) Ans+=DP[Sum-Calc(1)-Calc(4)];
        if(Sum>=Calc(2)+Calc(3)) Ans+=DP[Sum-Calc(2)-Calc(3)];
        if(Sum>=Calc(2)+Calc(4)) Ans+=DP[Sum-Calc(2)-Calc(4)];
        if(Sum>=Calc(3)+Calc(4)) Ans+=DP[Sum-Calc(3)-Calc(4)];
        if(Sum>=Calc(1)+Calc(2)+Calc(3)) Ans-=DP[Sum-Calc(1)-Calc(2)-Calc(3)];
        if(Sum>=Calc(1)+Calc(2)+Calc(4)) Ans-=DP[Sum-Calc(1)-Calc(2)-Calc(4)];
        if(Sum>=Calc(1)+Calc(3)+Calc(4)) Ans-=DP[Sum-Calc(1)-Calc(3)-Calc(4)];
        if(Sum>=Calc(2)+Calc(3)+Calc(4)) Ans-=DP[Sum-Calc(2)-Calc(3)-Calc(4)];
        if(Sum>=Calc(1)+Calc(2)+Calc(3)+Calc(4)) Ans+=DP[Sum-Calc(1)-Calc(2)-Calc(3)-Calc(4)];
        cout<<Ans<<endl;
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}