一共有 $4$ 种硬币。面值分别为 $c_1, c_2, c_3, c_4$。某人去商店买东西，去了 $tot$ 次。每次带 $d_i$ 枚 $c_i$ 硬币，买 $s$ 的价值的东西。请问每次有多少种付款方法。

输入格式

第一行包含 $5$ 个非负整数 $c_1, c_2, c_3, c_4, tot$ ($c_i \leq 10^5, tot \leq 1000$)。

接下来的 $tot$ 行，每行包含 $5$ 个非负整数 $d_1, d_2, d_3, d_4, s$ ($d_i, s \leq 10^5$)。

输出格式

题解

首先，看到这道题应该可以先想到是背包 DP，不过裸的背包 DP 复杂度会达到 $O(4ns)$ ($n$ 为原题中的 $tot$)，过不去。

换种角度，如果 $d_i$ 都充分大，那么就无需考虑硬币不够用的情况了，那么可以发现没有必要去做 $s$ 次 DP，只需做一次 DP 然后存下来即可。

首先，还是假装 $d_i$ 都充分大，做一次 DP，那么 $f_s$ 就表示可能会不够用的情况的方案数，那怎么求不够用的总方案数呢？

记命题 $P_i$ ($1 \leq i \leq 4$) 表示第 $i$ 种硬币不够用，则由容斥原理，我们只需要求若干总硬币不够用的情况即可。

比如说第 $i$ 种硬币不够用，那么就是说明第 $i$ 种硬币使用了至少 $d_i + 1$ 个，而这样的方案有多少种捏？显然要 $s \geq c_i (d_i + 1)$，那么剩余的 $s - c_i (d_i + 1)$ 可以随意分配，相当于是原问题的一个 (已解决的) 子问题。

当然，如果 $s < c_i (d_i + 1)$，那么说明这种硬币显然不会不够用，方案数当然为 $0$ 啦。并且，多个硬币的情况也是类似的。

于是利用容斥原理，只需要进行一次 DP 即可得到答案，时间复杂度 $O(4s + 2^4 n)$。

代码

#include <bits/stdc++.h>
#define N 100034
#define parity __builtin_parity
using namespace std;

typedef long long ll;

int n, q, s, i, j;
int c[4], d[4];

ll f[N], ans;

inline ll F(int x) {return x >= 0 ? f[x] : 0;}

int main(){
    scanf("%d%d%d%d%d", c, c + 1, c + 2, c + 3, &q);
    f[0] = 1;
    for(i = 0; i < 4; ++i)
        for(j = c[i]; j < N; ++j)
            f[j] += f[j - c[i]];
    for(; q; --q){
        scanf("%d%d%d%d%d", d, d + 1, d + 2, d + 3, &n);
        ++d[0]; ++d[1]; ++d[2]; ++d[3];
        for(ans = i = 0; i < 16; ++i){
            for(s = n, j = 0; j < 4; ++j)
                if(i >> j & 1)
                    s -= c[j] * d[j];
            ans += parity(i) ? -F(s) : F(s);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

坑

坑1：有哪些硬币不够用，就把哪些硬币所对应的价值减掉，再乘以 $(-1)^k$，其中 $k$ 是不够用的硬币的个数。注意在减去 DP 值的时候要满足 $s \geq \sum c_i (d_i + 1)$，否则直接为 $0$。

题目描述

输入格式

输出格式

题解

代码

坑