HAOI 硬币购物 - 容斥

链接:LUOGU P1450
难度 提高+
Description
某人一共有4种硬币，面值分别为。他去商店买东西，去了次。每次带枚面值为的硬币，买的价值的东西。
求每次有多少种付款方法。

Input Format
第一行 。
下面行，每行5个数，。

Output Format
每行一个数表示答案。

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

Constraints
对于%的数据，。

CCYOS
这是韩佳坤juju的题。【照抄论文预警_( : 3 _|||||||||||| _

1. 不看数据范围，会觉得这是一道裸的多重背包题。然而这道题不仅数据比较大而且还是多组数据。快乐.jpg
2. 于是考虑去掉这个的限制，发现完全背包似乎可行。此时计算得出的方案数里显然有很多是不符合条件的：设实际使用的硬币数量为，满足的方案集合为，补集转化，则其中可用容斥原理求解。
   由于只有4种硬币，保证复杂度。
   补集转化可行。
3. 容斥原理求解：
   公式：以求为例，即满足，即求解稍稍转化，强制不满足条件设，那么可以直接求解
4. 完全背包预处理即可。保证每组询问复杂度。
5. 会爆。

第一次打了一个神奇代码，输出和样例互为相反数，输出，A了。（我该说些什么好）
第二次仔细思考了一下，写了一个非常好理解的代码。注意由于是减去并，所以给答案更新时符号要变一下。
code

#include<bits/stdc++.h>
using namespace std;

int tot,s,coin[5],d[5];
long long f[100005];

inline int read(){
    char c = getchar();
    int fl = 1,ret = 0;
    for(;!isdigit(c) && c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

int main(){
    coin[1] = read();coin[2] = read();coin[3] = read();coin[4] = read();tot = read();
    f[0] = 1;
    for(int i = 1;i <= 4;++i)
        for(int j = coin[i];j <= 100000;++j)
            f[j] += f[j - coin[i]];
    for(int i = 1; i <= tot;++i){
        d[1] = read();d[2] = read();d[3] = read();d[4] = read();s = read();
        long long ans = f[s];//总方案
        for(int j = 1;j < 16;++j){//二进制枚举方案 0001 - 1111
            int ss = s,cnt = 0;//ss即s'，cnt表示集的数量方便容斥
            for(int k = 0;k < 4;++k)
                if((j >> k)&1)ss -= (d[k + 1] + 1) * coin[k + 1],++cnt;
            if(ss < 0)continue;//注意判无解
            if(cnt & 1)ans -= f[ss];
            else ans += f[ss];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

还可以写得更好看。
把的初始化放进循环里，即从开始循环。
还可以把换成 ^= 来记录单复，位运算太美妙了。