硬币购物一共有$4$种硬币。面值分别为$c1,c2,c3,c4$。某人去商店买东西，去了$tot$次。每次带$di$枚$ci$硬币，买$si$的价值的东西。请问每次有多少种付款方法。
直接考虑有多少种方案数可行有点儿难，这时候就应该考虑容斥原理，即有多少人不可行，计算出总的方案数，容斥一下即可。
使用完全背包，计算总的方案数。
然后枚举每一种可能的情况，用总的方案数-第一枚硬币超过的方案数-第二枚。。。+第一枚和第二枚同时超过的方案数。。。以此类推
#include<bits/stdc++.h> #define N 1000000 #define LL long long using namespace std; int c[5],T,S,d[5]; LL f[N]; int main() { for(int i=1;i<=4;i++) scanf("%d",&c[i]); f[0]=1; for(int i=1;i<=4;i++) for(int j=c[i];j<=N/10+10;j++) f[j]+=f[j-c[i]]; scanf("%d",&T); while(T--) { for(int i=1;i<=4;i++) scanf("%d",&d[i]); scanf("%d",&S); LL ans=f[S]; for(int k=0,i=1;i<=15;i++){ LL now=S;k=0;//注意,k一定要还原 for(int j=1;j<=4;j++){ if((1<<(j-1))&i) k^=1,now-=(d[j]+1)*c[j]; } if(now>=0) k?ans-=f[now]:ans+=f[now]; } printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/song-/p/9789098.html