Luogu 1450 [HAOI2008]硬币购物

优美的dp + 容斥。

首先可以不用考虑数量限制，处理一个完全背包$f_{i}$表示用四种面值的硬币购买的方案数，对于每一个询问，我们考虑容斥。

我们的$f_{s}$其实多包含了$f_{s - c_{i} * (d_{i} + 1)}$，所以我们把这些减去（这个式子的意思可以看成把$d_{i} + 1$以上的数全部都删掉做一个完全背包，就是只选$d_{i}$个），然而这样多减掉了同时选择两个的，又多加了同时选择三个的……

写成位运算就很优美啦。

时间复杂度$O(maxS + |s| * 2^{|s|} * tot)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e5 + ;

int testCase, c[], d[];

ll f[N];

template <typename T>

inline void read(T &X) {

    X = ;

    char ch = ;

    T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

int main() {

    for(int i = ; i <= ; i++) read(c[i]);

    f[] = ;

    for(int i = ; i <= ; i++)

        for(int j = c[i]; j <= ; j++)

            f[j] += f[j - c[i]];

/*    for(int i = 0; i <= 20; i++)

        printf("%lld ", f[i]);

    printf("\n");    */

    for(read(testCase); testCase--; ) {

        for(int i = ; i <= ; i++) read(d[i]);

        int s; read(s);

        ll res = ;

        for(int i = ; i <= ; i++) {

            ll tot = s; bool flag = ;

            for(int j = ; j < ; j++)

                if(i & ( << j)) flag ^= , tot -= c[j + ] * (d[j + ] + );

            if(tot < ) continue;

            if(flag) res -= f[tot];

            else res += f[tot];

        }

        printf("%lld\n", res);

    }

    return ;

}