bzoj1042: [HAOI2008]硬币购物

容斥原理。 算出不限制硬币数量的方案，-限制1+限制2-限制3+限制4。

限制就是用d+1个硬币。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100000+10;

long long f[maxn],res;
int t,c[5],d[5];

void dfs(int dep,int sum,int k) {
    if(dep==5) {
        if(k&1) res-=f[sum];
        else res+=f[sum];
    }
    else {
        dfs(dep+1,sum,k);
        if(c[dep]*(d[dep]+1)<=sum) 
            dfs(dep+1,sum-c[dep]*(d[dep]+1),k+1);
    }
}

int main() {
    for(int i=1;i<=4;i++) scanf("%d",&c[i]);
    scanf("%d",&t);
    f[0]=1;
    for(int i=1;i<=4;i++) 
    for(int j=c[i];j<maxn;j++)
        f[j]+=f[j-c[i]];
    
    for(int i=1,s;i<=t;i++) {
        for(int j=1;j<=4;j++) scanf("%d
",&d[j]);
        scanf("%d",&s);
        res=0;
        dfs(1,s,0);
        printf("%lld
",res);
    }
    return 0;
}