一边听课一边打摆
因为每次都做一次背包会$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
|
using namespace std;
const int maxn=100007;
int s,tot,c[4],d[4];
long long f[maxn]={1};
int () {
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("%lldn",ans);
}
return 0;
}
|
近期评论