博客

Description
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
Input
第一行 c1,c2,c3,c4,tot
下面tot行 d1,d2,d3,d4,s
Output
每次的方法数
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27
HINT
数据规模
di,s<=100000
tot<=1000
Source

基本思路：先预处理出来没有限制时的方案数（完全背包），然后利用容斥原理$ans=$价值为$s$时的方案数（超过限制）$-\sum$（一种硬币超过限制）$+\sum$（两种硬币超过限制）$-\sum$（三种硬币超过限制）+$\sum$（四种硬币超过限制）。
这里可以用位运算（共$2^4$种）来枚举所有方案。
（注意：一定要开$long long$）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int S=100010;
long long f[S];
int c[10],d[10],s,tot;
void in(int &x)
{
    int f=1;x=0;char t=getchar();
    while((t<48)or(t>57)){if(t=='-')f=-1;t=getchar();}
    while((t>=48)and(t<=57)){x=x*10+t-48;t=getchar();}
    x*=f;
}
void work()
{
    f[0]=1;
    for (int i=1;i<=4;++i)
        for (int j=0;j<S;++j)
        if (j>=c[i]) f[j]+=f[j-c[i]];
}
int main()
{
    for (int i=1;i<=4;++i) in(c[i]);
    in(tot);work();
    while(tot)
    {
        for (int i=1;i<=4;++i) in(d[i]);
        in(s);long long ans=0;
        for (int i=0;i<(1<<4);++i)
        {
            int num=0,x=s;
            for (int j=1;j<=4;++j)
            if ((i>>(j-1))&1)//取出从后往前数第j位
            {
                x-=(d[j]+1)*c[j];
                ++num;
            }
            if (x>=0)
                if (num&1) ans-=f[x];
                else ans+=f[x];
        }
        printf("%lld\n",ans);
        --tot;
    }
    return 0;
}