组合数学

组合数学

例1.硬币购物

原题链接

解：这道题目的dp非常巧妙，如果看不懂就死记硬背下来吧。

由于这道题目中中硬币的面值是给定且不会发生变化的。所以我们可以利用完全背包，预处理出$dp[i]$，$dp[i]$表示组成$i$元一共有几种方式（没有限制）。

但是这道问题是有限制的。我们如何利用没有限制的方案数去推导有限制的方案数呢？答案是利用容斥原理。

例如说，对于$i$物品，有$d[i]$的限制，如果我们只考虑这一个物品有限制的话，我们完全可以强行取出$d[i]+1$个面值为$c[i]$的硬币。所以对于有$d[i]$限制的物品，我们的方案数就是$dp[i-(d[i]+1)\times c[i]]$。

再解释以下这里的$dp[i-(d[i]+1)\times c[i]]$是怎么得到的。为什么$dp[j-(d[i]+1)\times c[i]]$中会存在选择$(d[i]+2)\times c[i]$的情况？因为有$(d[i]+1)\times c[i] \lt (d[i]+2)\times c[i] \Rightarrow (j-(d[i]+1) \times c[i]) \gt (j-(d[i]+2) \times c[i])$。所以说$dp[j-(d[i]+1)\times c[i]]$是包含了这种情况的。

而对于整个答案的容斥，事实上就是$无限制的情况-(有一个限制)+(有两个限制)-……$，这就是最简单的容斥原理了。

void solve() {
    vector<int> c(4);
    for (int i = 0;i < 4;i++) c[i] = read();
    vector<int> dp(1e5 + 10, 0);
    dp[0] = 1;
    for (int i = 0;i < 4;i++) {
        for (int j = c[i];j <= 1e5;j++)
            dp[j] += dp[j - c[i]];
    }

    int T = read();
    while (T--) {
        vector<int> d(4);
        for (int i = 0;i < 4;i++) d[i] = read();
        int s = read(), ans = 0;
        for (int status = 0;status <= 15;status++) {
            int cnt = 0;
            for (int i = 0;i < 4;i++) {
                if (status & (1 << i)) {
                    cnt += (d[i] + 1) * c[i];
                }
            }
            if (s - cnt < 0) continue;
            if (__popcount(status) & 1) {
                ans -= dp[s - cnt];
            } else {
                ans += dp[s - cnt];
            }
        } 
        printf("%lld\n", ans);
    }
}