[HAOI2008]硬币购物

Posted on | In

一边听课一边打摆

因为每次都做一次背包会$T$飞，考虑先不考虑限制预处理方案数

然后考虑限制，用总方案数减去不合法的方案数

第$i$种硬币要超出限制至少要用$d[i]+1$个

那么考虑限制之后不合法的方案数就是$F[s-c[i]*(d[i]+1)]$

最后对硬币进行容斥，计算答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int maxn=100007;
int s,tot,c[4],d[4];
long long f[maxn]={1};
int main () {
    for(register int i=0;i<4;++i) scanf("%d",&c[i]);
    for(register int i=0;i<4;++i)
        for(register int j=c[i];j<maxn;++j) f[j]+=f[j-c[i]];
    scanf("%d",&tot);
    while(tot--) {
        for(register int i=0;i<4;++i) scanf("%d",&d[i]);
        scanf("%d",&s); register long long ans=0;
        for(register int i=0;i<16;++i) {
            register int num=0;
            register long long sum=0;
            for(register int j=0;j<4;++j)
                if(i&(1<<j)) ++num,sum+=c[j]*(d[j]+1);
            if(s<sum) continue ;
            ans+=(num&1)?-f[s-sum]:f[s-sum];
        }
        printf("%lld\n",ans);
    }
    return 0;
}