分析

背包 题。因为朴素的 的时间复杂度为 应该过不去。那么换种思路，先考虑没有个数限制，令 为考虑前 种物品，体积为 时，总的方案数。发现我们对个数的限制可以考虑子集容斥。考虑到，恰好选 个的方案数是等于至少选 个的方案数减去至少选 的方案数。那么现在是让我们求恰好选 到 个的方案数，左式求个和，那么右式错位相消，那么至多选 的方案数为 ，最后考虑下一种的时候直接递归，要注意容斥系数也要变符号，时间复杂度为 。

• 计算时可以滚动数组优化一下空间。
• 要想到恰好选 个的方案数是等于至少选 个的方案数减去至少选 的方案数。这道题就不难了。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define LL long long
  LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
  }
  const int N = 101000,M = 100000;
  LL c[5],tot,d[5],f[N],s,ans;
  void solve(LL i,LL S,LL opt) {
    if(S < 0) return;
    if(i == 5) {ans = (ans + opt * f[S]);return;};
    solve(i+1,S,opt);solve(i+1,S-((d[i] + 1)*c[i]),-1 * opt);
  }
  int main() { 
    f[0] = 1;
    for(int i = 1;i <= 4;i++) {
        c[i] = read(); 
        for(int j = c[i];j <= M;j++) f[j] = f[j] + f[j - c[i]]; 
    }
    tot = read();
    while(tot--) {
        for(int i = 1;i <= 4;i++) d[i] = read();
        s = read();ans = 0;
        solve(1,s,1);
        printf("%lld\n", ans);
    }
  }
  

```