BZOJ-1042: [HAOI2008]硬币购物

Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s的价值的东西。请问每次有多少种付款方法。di,s<=100000,tot<=1000

我们可以直接求出每种货币不计数量的方案数。
发现答案其实就是各种方案数的容斥。总方案数-有一个用超了的方案数+有两个......
中间过程可能会爆int。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll c[10],d[10],tot,s,f[110000];
void cal()
{
    f[0]=1;
    for(int i=1;i<=4;i++)
        for(int j=c[i];j<=100000;j++) f[j]+=f[j-c[i]];
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&c[1],&c[2],&c[3],&c[4],&tot);
    cal();
    while(tot--)
    {
        scanf("%lld%lld%lld%lld%lld",&d[1],&d[2],&d[3],&d[4],&s);
        ll ans=f[s];
        for(int i=1;i<=4;i++) d[i]++;
        for(int i=1;i<=4;i++) if(s-c[i]*d[i]>=0) ans-=f[s-c[i]*d[i]];
        for(int i=1;i<4;i++)
            for(int j=i+1;j<=4;j++)
                if(s-c[i]*d[i]-c[j]*d[j]>=0)
                    ans+=f[ s-c[i]*d[i]-c[j]*d[j] ];
        for(int i=1;i<=4;i++)
        {
            ll tmp=s;
            for(int j=1;j<=4;j++) if(j!=i) tmp-=c[j]*d[j];
            if(tmp>=0) ans-=f[tmp];
        }
        for(int i=1;i<=4;i++) s-=c[i]*d[i];
        if(s>=0) ans+=f[s];
        printf("%lld\n",ans);
    }
    return 0;
}