题目：
dp预处理+容斥原理。
先预处理求出无限制的各面值的组成方案数 f (完全背包)。
求s [ i ]有限制的，就是s [ i ]无限制方案数 - 单种硬币一定超过限制的方案数 + 两种的 - 三种的 + 四种的。
第 k 中硬币一定超过限制的方案数就是f [ s [ i ] - c [ k ] * ( d [ k ] + 1 ) ]，即确定用了 d + 1 个该硬币，刨去它们后的无限制方案数。
当 c [ k ] * ( d [ k ] + 1 ) > s [ i ] 时不用操作，即没有“超过该限制”的可能。但== s [ i ] 时还是要操作的，f [ 0 ] = 1。
以为要用高精度，结果WA。看看题解发现不用高精度，于是……
如果高精度的话，防止某次减到了负数，可以先把加的弄了（反正只有四种硬币）。
非高精AC代码：
#include#include using namespace std;typedef long long ll;ll c[5],d[1005][5],tot,mx,s[1005],f[100005],ans;void pre(){ f[0]=1;/// for(int i=1;i<=4;i++) for(ll j=c[i];j<=mx;j++) f[j]+=f[j-c[i]];}void dfs(ll now,ll k,ll cnt,ll z)//第now次询问，第k号，选了cnt个，f目前脚标 { if(z<0)return;//不是z<=0!! if(k==5) { if(cnt&1)ans-=f[z]; else if(cnt)ans+=f[z]; return; } dfs(now,k+1,cnt,z); dfs(now,k+1,cnt+1,z-c[k]*d[now][k]-c[k]);}int main(){ for(int i=1;i<=4;i++)scanf("%lld",&c[i]); scanf("%lld",&tot); for(int i=1;i<=tot;i++) scanf("%lld%lld%lld%lld%lld",&d[i][1],&d[i][2],&d[i][3],&d[i][4],&s[i]),mx=max(mx,s[i]); pre(); for(int i=1;i<=tot;i++) { ans=f[s[i]]; dfs(i,1,0,s[i]); printf("%lld\n",ans); } return 0;}
高精WA代码：
#include#include #include using namespace std;typedef long long ll;const int INF=100005;ll c[5],d[1005][5],tot,s[1005],mx,tp;int f[INF][205],ans[205];void plu(ll k,int a[],int b[]){ int tmp[205]={ 0},lm=max(a[0],b[0]); for(int i=1;i<=lm;i++) { tmp[i]+=a[i]+b[i]; if(tmp[i]>10)tmp[i]-=10,tmp[i+1]++; } tmp[0]=lm; if(tmp[tmp[0]+1])tmp[0]++; memcpy(f[k],tmp,sizeof tmp);}void pre(){ f[0][1]=1;f[0][0]=1; for(int i=1;i<=4;i++) for(ll j=c[i];j<=mx;j++) plu(j,f[j],f[j-c[i]]);}void print(){// printf("(%d)",ans[0]); for(int i=ans[0];i;i--) printf("%d",ans[i]); printf("\n");}void plu2(ll k){ int lm=max(ans[0],f[k][0]); for(int i=1;i<=lm;i++) { ans[i]+=f[k][i]; if(ans[i]>10)ans[i]-=10,ans[i+1]++; } if(ans[ans[0]+1])ans[0]++;// printf("++ k=%d ",k);print();}void jian(ll k){// int lm=max(ans[0],f[k][0]); for(int i=1;i<=f[k][0];i++) { ans[i]-=f[k][i]; if(ans[i]<0)ans[i]+=10,ans[i+1]--; } while(!ans[ans[0]]&&ans[0]>1)ans[0]--;// printf("-- k=%d ",k);print();}//void debugprint()//{// for(int i=1;i<=s[1];i++)// {// printf("i=%d ",i);// for(int j=f[i][0];j;j--)// printf("%d",f[i][j]);// printf("\n");// }//}int main(){ for(int i=1;i<=4;i++)scanf("%lld",&c[i]); scanf("%lld",&tot); for(int i=1;i<=tot;i++) { scanf("%lld%lld%lld%lld%lld",&d[i][1],&d[i][2],&d[i][3],&d[i][4],&s[i]); mx=max(mx,s[i]); } pre(); for(int i=1;i<=tot;i++) { memcpy(ans,f[s[i]],sizeof f[s[i]]);//// debugprint(); for(int u=1;u<4;u++) for(int v=u+1;v<=4;v++) { tp=c[u]*d[i][u]+c[v]*d[i][v]+c[u]+c[v]; if(tp<=s[i])plu2(s[i]-tp); ///<=!!!，因为我的f[0]有值为1 ;正是要用这个1！ } tp=c[1]*d[i][1]+c[2]*d[i][2]+c[3]*d[i][3]+c[4]*d[i][4]+c[1]+c[2]+c[3]+c[4]; if(tp<=s[i])plu2(s[i]-tp); for(int u=1;u<=4;u++) { tp=c[u]*d[i][u]+c[u]; if(tp<=s[i])jian(s[i]-tp); } for(int u=1;u<=2;u++) for(int v=u+1;v<=3;v++) for(int j=v+1;j<=4;j++) { tp=c[u]*d[i][u]+c[v]*d[i][v]+c[j]*d[i][j]+c[u]+c[v]+c[j]; if(tp<=s[i])jian(s[i]-tp); } print(); } return 0;}