[数据结构与算法]P1450 [HAOI2008] 容斥原理 + DP

题意

传送门 P1450 [HAOI2008]硬币购物

题解

求满足 $\sum x_k{c}_k=s$ 的非负整数解个数。令 $S_k$ 代表满足 $x_k\le d_k$ 的解集。问题即求
$$\cap S_k=\overline{\cup \overline{S_k}}$$ 则转换为存在下界约束的方程，以 $\overline{S_k}$ 为例，下界约束 $x_k\ge d_k+1$，$s$ 减去下界约束后转换为无约束问题，DP 求解即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAXS = 1E5 + 5;
ll dp[5][MAXS];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int c[4], n;
    for (int i = 0; i < 4; ++i)
        cin >> c[i];
    dp[0][0] = 1;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < MAXS; ++j)
        {
            if (j - c[i] >= 0)
                dp[i + 1][j] += dp[i + 1][j - c[i]];
            dp[i + 1][j] += dp[i][j];
        }
    cin >> n;
    while (n--)
    {
        int d[4], s;
        for (int i = 0; i < 4; ++i)
            cin >> d[i];
        cin >> s;
        ll sum = 0;
        for (int i = 0; i < 1 << 4; ++i)
        {
            ll rem = s, cnt = 0;
            for (int j = 0; j < 4; ++j)
                if (i >> j & 1)
                    ++cnt, rem -= (ll)c[j] * (d[j] + 1);
            if (rem >= 0)
                sum += (cnt & 1 ? -1 : 1) * dp[4][rem];
        }
        cout << sum << '\n';
    }
    return 0;
}