1042: [HAOI2008]硬币购物
题意：4种硬币。面值分别为c1,c2,c3,c4。1000次询问每种硬币di个，凑出(sle 10^5)的方案数
完全背包方案数？ 询问太多了
看了题解
只有4种物品，每种物品有数量限制
不考虑数量限制，(f(i))凑出i的方案数，一遍完全背包就行了，注意先枚举物品
然后对于超过限制容斥:
[都不超过限制=所有方案- ge 1个超限制+ge 2个超限制-...
]
i超限制就是i至少选了(d_i+1)个，其他任意选
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int c[5],d[5],sum;
ll f[N];
int main() {
//freopen("in","r",stdin);
for(int i=1; i<=4; i++) c[i]=read();
f[0]=1;
for(int i=1; i<=4; i++)
for(int j=c[i]; j<=1e5; j++) f[j] += f[j-c[i]];
int T=read(), All=1<<4;
for(int i=1; i<=T; i++) {
for(int i=1; i<=4; i++) d[i]=read();
sum=read(); ll ans=0;
for(int s=0; s<All; s++) {
int one=0;ll val=sum;
for(int i=0; i<4; i++) if(s&(1<<i)) one++, val-=(ll)(d[i+1]+1)*c[i+1];
if(val>=0) ans += (one&1) ? -f[val] : f[val];
}
printf("%lld
",ans);
}
}