手动容斥

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXS = 100000;
int c[5], n, d[5], cd[5], s;
int f[MAXS + 5]; // f[i]: 不考虑硬币数量限制时，i块钱有几种方案
int cal()
{
    for (int i = 1; i <= 4; i++)
        cd[i] = c[i] * (d[i] + 1);
    int ans = f[s];
    if (s >= cd[1])
        ans -= f[s - cd[1]];
    if (s >= cd[2])
        ans -= f[s - cd[2]];
    if (s >= cd[3])
        ans -= f[s - cd[3]];
    if (s >= cd[4])
        ans -= f[s - cd[4]];
    if (s >= cd[1] + cd[2])
        ans += f[s - cd[1] - cd[2]];
    if (s >= cd[1] + cd[3])
        ans += f[s - cd[1] - cd[3]];
    if (s >= cd[1] + cd[4])
        ans += f[s - cd[1] - cd[4]];
    if (s >= cd[2] + cd[3])
        ans += f[s - cd[2] - cd[3]];
    if (s >= cd[2] + cd[4])
        ans += f[s - cd[2] - cd[4]];
    if (s >= cd[3] + cd[4])
        ans += f[s - cd[3] - cd[4]];
    if (s >= cd[1] + cd[2] + cd[3])
        ans -= f[s - cd[1] - cd[2] - cd[3]];
    if (s >= cd[1] + cd[2] + cd[4])
        ans -= f[s - cd[1] - cd[2] - cd[4]];
    if (s >= cd[1] + cd[3] + cd[4])
        ans -= f[s - cd[1] - cd[3] - cd[4]];
    if (s >= cd[2] + cd[3] + cd[4])
        ans -= f[s - cd[2] - cd[3] - cd[4]];
    if (s >= cd[1] + cd[2] + cd[3] + cd[4])
        ans += f[s - cd[1] - cd[2] - cd[3] - cd[4]];
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i++)
        for (int j = c[i]; j <= MAXS; j++)
            f[j] += f[j - c[i]];
    while (n--)
    {
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        cout << cal() << "\n";
    }

    return 0;
}

位运算枚举子集计算容斥

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXS = 100000;
int c[5], n, d[5], cd[5], s;
int f[MAXS + 5]; // f[i]: 不考虑硬币数量限制时，i块钱有几种方案
int cal()
{
    for (int i = 1; i <= 4; i++)
        cd[i] = c[i] * (d[i] + 1);
    int ans = 0;
    for (int sta = 0; sta <= (1 << 4) - 1; sta++)
    {
        int flag = 1;
        int nowSum = 0;
        for (int i = 1; i <= 4; i++)
            if (sta & (1 << (i - 1)))
            {
                // 当前状态右数第 i 位是 1
                flag = -flag;
                nowSum += cd[i];
            }
        if (s >= nowSum)
            ans += flag * f[s - nowSum];
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i++)
        for (int j = c[i]; j <= MAXS; j++)
            f[j] += f[j - c[i]];
    while (n--)
    {
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        cout << cal() << "\n";
    }
    return 0;
}