[容斥原理]Bzoj1042 硬币購物[HAOI2008]

先用遞推算出硬币無限的所有方案數，然後,因為一個硬币超限的最小個數是d[i]+1,能使硬币超限的最小錢數是c[i](d[i]+1),對于一個硬币超限的所有情況就是f[sum-c[i](d[i]+1)]，然而4個硬币超限的情況并是有重疊關系，這就用到容斥原理的關系，奇數個就-,偶數個就加

#include<cstdio>
#include<cstring>
#define maxn 100010

int m,t,c[],d[],qian;
long long f[maxn],ans;

void dt()
{
    f[]=;
    for(int i=;i<=;i++)
        for(int j=c[i];j<=;j++)
            f[j]+=f[j-c[i]];
}

void prework()
{
    for(int i=;i<=;i++)
        scanf("%d",&d[i]);
    scanf("%d",&qian);
}

void dfs(int x,int k,int sum)
{
    if(sum<)
        return;
    if(x==)
    {
        if(k%)
            ans-=f[sum];
        else
            ans+=f[sum];
        return;
    }
    dfs(x+,k+,sum-(d[x]+)*c[x]);
    dfs(x+,k,sum);
}

void mainwork()
{
    ans=;
    dfs(,,qian);
}

void print()
{
    printf("%lld\n",ans);
}

int main()
{
    for(int i=;i<=;i++)
        scanf("%d",&c[i]);
    scanf("%d",&t);
    dt();
    for(int i=;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return ;
}