HAOI 硬币购物 - 容斥

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

Input Format
第一行 $c_1,c_2,c_3,c_4,tot$ 。
下面 $tot$ 行，每行5个数， $d1,d2,d3,d4,s$ 。

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

Sample Input

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

Sample Output

4
27

Constraints
对于 $100$ %的数据， $tot \leq 1000,n \leq 10^5,d_i \leq 10^5$ 。

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

不看数据范围，会觉得这是一道裸的多重背包题。然而这道题不仅数据比较大而且还是多组数据。快乐.jpg

于是考虑去掉这个 $d_i$ 的限制，发现完全背包 $O(n)$ 似乎可行。此时计算得出的方案数里显然有很多是不符合条件的：设实际使用的硬币数量为 $x_i$ ，满足 $x_i > d_i$ 的方案集合为 $S_i$ ，补集转化，则 $ans = f[s] - |S_1 \cup S_2 \cup S_3 \cup S_4|$ 其中 $|S_1 \cup S_2 \cup S_3 \cup S_4|$ 可用容斥原理求解。
由于只有4种硬币，保证复杂度。
补集转化可行。

容斥原理求解：
公式： $|S_1 \cup S_2 \cup … \cup S_n| = \sum{|S_i|}-\sum_{i < j}{|S_i \cap S_j|}+\sum_{i <j <k}{S_i \cap S_j \cap S_k|}+…+(-1)^{n + 1} ·|S_1 \cap … \cap S_n|$ 以求 $S_1$ 为例，即满足 $x_1 > d_1$ ，即求解 $c_1 · x_1 + c_2·x_2 + c_3 · x_3 + c_4·x_4 = s,x_1 > d_1 + 1$ 稍稍转化，强制不满足条件设 $s'$ ， $s' = s - c_1·(d_1 + 1)$ 那么可以直接求解 $c_1 · x_1' + c_2·x_2 + c_3 · x_3 + c_4·x_4 = s'$

完全背包 $O(4m)$ 预处理即可。 $m=10^5$ 保证每组询问复杂度 $O(16)$ 。

会爆 $int$ 。

第一次打了一个神奇代码，输出和样例互为相反数， $-ans$ 输出，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;
}

还可以写得更好看。
把 $ans = f[s]$ 的初始化放进循环里，即 $j$ 从 $0$ 开始循环。
还可以把 $++cnt$ 换成 $cnt$ ^= $1$ 来记录单复，位运算太美妙了。

HAOI 硬币购物 - 容斥

推荐阅读更多精彩内容