P1450 [HAOI2008] 硬币购物
已经八百年没写过题解了。
先是因为懒，后是没有时间写了。
但是这题印象属实深刻。任务列表里吃灰两个月
想到了完全背包然后容斥 bulabula 的
但是就是不知道该怎么下手。
好像也没那么复杂。
先预处理出购买价值 \(i\) 的东西的方案数，先不管限不限制个数。
然后把不合法的部分减去。
这个可以预处理出来，直接完全背包就行了。
那么什么是不合法的部分？
即要排除 \(> d_i\) 的情况，也就是 \(\geq d_i+1\) 的情况，这部分的价值是 $ s- (d_i+1)\times c_i$，之前处理出了价值 \(i\) 的方案数，那这个是直接可以搞的, 然后容斥的加减即可。
具体的容斥证明可以看 https://www.luogu.com.cn/discuss/481921
以及不是多么困难的码。
// Problem: P1450 [HAOI2008] 硬币购物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1450
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Gym_nastics
//
// Powered by CP Editor (https://cpeditor.org)
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define INF 0x3f3f3f3f
#define best cout<<"whw is a hreo\n";
#define int long long
const int mod=1e9+7;
const int maxn=1e6+7,maxm=2e3+1;
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
int f[maxn+1],c[5],d[5],n;
#define cl(x) (d[x]+1)*c[x]
signed main() {
for(int i=0;i<4;i++) c[i]=read();
f[0]=1;
for(int i=0;i<4;i++)
for(int j=c[i];j<=maxn-5;j++) f[j]+=f[j-c[i]];
n=read();
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++) d[j]=read();int s=read();
int res=f[s];
for(int j=1;j<16;j++){
int k=0,sum=s;
for(int l=0;l<4;l++) if(j&(1<<l)) k^=1,sum-=cl(l);
if(sum>=0) res+=k?-f[sum]:f[sum];
}
printf("%lld\n",res);
}
return 0;
}