[HAOI2018]硬币购物

都这年头了，还有谁购物用硬币的吗？

题目大意

首先，你有四种面值的硬币

然后你会出门采购次

每次出门，你都会带上一些硬币，每种硬币的个数给定

然后你买了的东西

问你有多少种付款的方案

分析

直接写裸的背包的时间复杂度直接炸天

那么正难则反是一个十分优秀的想法

就是说，可以不计代价的用总的方案减去不合法的方案

那么剩下的全是合法的了

那么，就要分别统计

这四种硬币构成的所有集合的不合法的方案

及当且仅当上述集合中的种类的硬币不满足条件是的总方案数

怎么求？

首先，可以用到二进制枚举子集，得到上述个集合

然后考虑容斥

可以得到，子集大小为奇数的容斥系数为，而偶数的容斥系数为

那么这部分可以表示如下：

inline void Solve()
{
        for (int i = 1; i < 16; ++i) {
            int size = tot;
            cke = 0;
            for (int state = i, j(0); state; ++j, state >>= 1)
                if (state & 1) cke ^= 1, size -= s[j] * (d[j] + 1);
            if (size >= 0) {
                if (cke & 1) ans -= f[size];
                else ans += f[size];
            }
        }
}

那么最后用整体减一下就可以了

code

signed main()
{
    for (int i = 0; i < 4; ++i) {
        s[i] = __read();
        for (int j = s[i]; j < maxn; ++j)
            f[j] += f[j - s[i]];
    }
    int T = __read();

    while (T--) {
        for (int i = 0; i < 4; ++i)
            d[i] = __read();

        int tot = __read(), cke(0);
        ll ans(f[tot]);
        Solve();
        printf ("%lld\n", ans);
    }
    system("pause");
}