洛谷题目传送门
我实在是太弱了，第一次正儿八经写背包DP，第一次领会如此巧妙的容斥原理的应用。。。。。。
对每次询问都做一遍多重背包，显然T飞，就不考虑了
关键就在于每次询问如何利用重复的信息
我这么弱，当然是想不到容斥原理的啦
暂且先当成完全背包，每种硬币可使用无限次，预处理\(f\)数组，\(f[i]\)等于买价值\(i\)的东西的总方案数
然后就要从中减去不合法的。首先肯定会有一种硬币超额使用，第\(j\)中硬币等于说强制选了\(d_j+1\)个，剩下的依然随便选，那么第
\(j\)种硬币超额的不合法的方案数等于\(f[s-(d_j+1)*c_j]\)，于是从答案里减去\(\sum_{j=1}^4f[s-(d_j+1)*c_j]\)
还要注意，第一种第二种都超额、第一种第三种都超额、第一种第四种都超额、第二种第三种都超额、第二种第四种都超额、第三种第四种都超额的方案在上一步中都被减了两次，所以额外都加一次回来。。。。。。（接着把容斥做下去就不说了）
复杂度降到\(O(4maxs+4×2^4tot)\)，轻松通过
注意开longlong就好啦
#include<cstdio>
#define R register
typedef long long LL;
const int S=100009;
LL f[S]={1ll};
int main(){
R int c[4],d[4],tot,i,j,k,now,s,ss,tmp;
R LL ans;
for(j=0;j<4;++j)scanf("%d",&c[j]);
scanf("%d",&tot);
for(j=0;j<4;++j)
for(i=c[j];i<S;++i)
f[i]+=f[i-c[j]];//完全背包预处理
while(tot--){
for(j=0;j<4;++j)scanf("%d",&d[j]);
scanf("%d",&s);
ans=f[s];
for(ss=1;ss<=15;++ss){//二进制数枚举集合，容斥
now=s;
for(tmp=ss,j=k=0;tmp;tmp>>=1,++j)
if(tmp&1)k^=1,now-=(d[j]+1)*c[j];
//注意k的作用，判断奇偶
if(now>=0)k?ans-=f[now]:ans+=f[now];
}
printf("%lld\n",ans);
}
return 0;
}