题意：
共有 4 种硬币。面值分别为
c
1
,
c
2
,
c
3
,
c
4
c_1,c_2,c_3,c_4
c1,c2,c3,c4。
某人去商店买东西，去了
n
n
n 次，对于每次购买，他带了
d
i
d_i
di 枚
i
i
i 种硬币，想购买
s
s
s的价值的东西。请问每次有多少种付款方法。
范围&性质：
1
≤
n
≤
1
0
3
,
1
≤
c
,
d
,
s
≤
1
0
5
1\le n\le 10^3,1\le c,d,s\le 10^5
1≤n≤103,1≤c,d,s≤105
分析：
不考虑个数限制时就是个很裸的完全背包，但是加上了限制那么我们就考虑将不合法的方案全都减掉，对于一个物品
i
i
i不合法的方案数可以看做第
i
i
i个物品被强制选了
d
[
i
]
+
1
d[i]+1
d[i]+1剩下的又可以看做一个没有限制的完全背包，然后对于每一种情况容斥原理组合到一起
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 1e5+5;
long long f
[maxn
],c
[5],d
[5];
long long ans
;
int t
,s
;
void work()
{
scanf("%lld%lld%lld%lld%d",&c
[1],&c
[2],&c
[3],&c
[4],&t
);
f
[0]=1;
for(int i
=1;i
<=4;i
++)
{
for(int j
=c
[i
];j
<=100000;j
++)
{
f
[j
]+=f
[j
-c
[i
]];
}
}
while(t
--)
{
scanf("%lld%lld%lld%lld%d",&d
[1],&d
[2],&d
[3],&d
[4],&s
);
ans
=f
[s
];
for(int i
=1,sum
,j
,k
,tmp
;i
<=15;i
++)
{
sum
=s
;
for(j
=1,k
=1,tmp
=i
;tmp
;tmp
>>=1,j
++)
{
if(tmp
&1) k
^=1,sum
-=(d
[j
]+1)*c
[j
];
}
if(sum
>=0) k
?ans
+=f
[sum
]:ans
-=f
[sum
];
}
printf("%lld\n",ans
);
}
}
}
int main()
{
zzc
::work();
return 0;
}
