题目
题解
先跑一遍完全背包，然后对于第 \(i\) 种物品只能有 \(d_i\) 枚硬币容斥一下。具体的：（强制 \(k\) 个硬币超出限制）
\[\sum_{T \subset D,|T|=k} (-1)^k \sum_{j \in T} f[s-c_i(d_i+1)] \]（其中，\(D\) 是 \(4\) 种硬币构成的集合，\(f[i]\) 是完全背包后，\(i\) 体积有多少种凑成方式）
时间复杂度 \(O(ns)\)。
代码
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 1e5+7;
int s;
int c[N],d[N],f[N];
void work() {
memset(f, 0, sizeof(f));
for(int i=0;i<4;++i) d[i] = read();
s = read();
f[0] = 1;
for(int i=0;i<4;++i) {
for(int j=c[i];j<=s;++j) {
f[j] += f[j-c[i]];
}
}
int up = (1<<4) - 1;
int ans = 0;
for(int i=0;i<=up;++i) {
int lim = 0, sz = 0;
for(int j=0;j<4;++j) {
if(i & (1<<j)) {
lim += c[j]*(d[j]+1);
++sz;
}
}
if(lim <= s) ans += (sz&1 ? -1 : 1) * f[s-lim];
}
printf("%lld\n",ans);
}
signed main()
{
for(int i=0;i<4;++i) c[i] = read();
int T = read();
while(T--) work();
return 0;
}
/*
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
4
27
*/
总结
背包，容斥的灵活运用。