Luogu P1450 硬币购物（计数，容斥）

先考虑每个硬币有 无限 个的情况。

设 $dp[i][j]$ 为：使用 前 $i$ 种硬币，购买 价值为 $j$ 的物品的方案数，那么有：

$dp[i][j] = \sum\limits_{k=1}dp[i-1][j-c_i*k]$。

很明显，这是一个 无穷背包，所以可以直接优化为：

dp[0] = 1;
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= 1e5; j++) {
        if (j - c[i] >= 0) dp[j] += dp[j-c[i]];
    }
}

那么，现在考虑 只有一种硬币有限制 的情况：

由于 $dp[j]$ 都是从 $dp[j-c_i]$ （实际上就是从 $dp[j-k*c_i]$）转移过来的，那么我们只要把 硬币超出限制的转移情况 删掉即可！

所以，$dp[j] - dp[(d_i+1) * c_i]$ 就是答案了！

那么如果 多个硬币有限制 呢？考虑 容斥 ！

假设有 $3$ 种硬币，那我们就 减去 $1$ 种硬币超限的情况，加上 $2$ 种硬币超限的情况，减去 $3$ 种硬币超限的情况。

枚举这些情况，使用 bitmask 即可！(具体的见代码)

容斥中，每一项的符号根据 bitmask 中 bit 的个数来决定！

#include <bits/stdc++.h>
#define ll long long

const int mod = 1e9+7;
const int maxn = 1e5+5;

ll dp[maxn];
int arr[5];
int d[5];
int q,s;

int main() {
    for (int i = 1; i <= 4; i++) cin >> arr[i];
    cin >> q;

    dp[0] = 1;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 1e5; j++) {
            if (j - arr[i] >= 0) dp[j] += dp[j-arr[i]];
        }
    }


    while (q--) {
        for (int i = 1; i <= 4; i++) cin >> d[i];
        cin >> s;
        ll ans = dp[s];

        for (int mask = 1; mask <= (1<<4)-1; mask++) {  // 枚举容斥
            int cnt = 0;
            int cur = 0;
            for (int j = 1; j <= 4; j++) {
                if (mask & (1<<(j-1))) {
                    cur += ((d[j]+1) * arr[j]);
                    cnt++;  // 判断加号还是减号
                }
            }

            if (s >= cur) {
                if (cnt & 1) ans -= dp[s - cur];
                else ans += dp[s - cur];
            }
        }

        cout << ans << "\n";
    }
}