题目链接

https://www.luogu.com.cn/problem/P1450

题意

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$

某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚的 第 $i$ 种硬币,想购买价值为 $s$ 东西(不设找零)。请问每次有多少种付款方法。

其中,$1 \leq c_i,d_i,s \leq 10^5, 1 \leq n \leq 1000$

题解

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

设 $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";
    }
}

其他例题(TODO)