[HAOI2008]硬币购物

题面在这里

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

使用单调队列优化多重背包十分开心地获得了20分的好成绩
(O(4Ts))为什么我就松不过呢?

观察数据，物品数量(=4)，考虑对于物品数量的指数级算法，容斥
如果没有物品数量的限制，那么此题变成了一个完全背包问题，直接求解即可
现在的关键是物品的数量有限制，因此考虑如何去掉物品数量过多的一部分

考虑把总容量减去单件物品目前能够达到的最大容量(即(s-d_i imes c_i))，对剩下的空间做完全背包，
我们能够从这个方案数中得到仍然含有这个物品的方案数(使用(f[s][t])中(t)的二进制位表示物品状况)，
那么这个方案应该会等于开始的背包中这件物品数量过多的方案。

update:我还是太菜了。。。其实不用考虑s,这个方案就等于(f[s-(d_i+1) imes c_i])

我们使用总数-不合法，就会得到这件物品不超过(d_i)的方案数

接下来考虑有两种物品同时超过的情况
如果我们仅仅使用刚才的算法计算出(f[0][s]-sum_{i=1}^{4}f[2^{i-1}][s-c_i imes d_i]),
那么一种有两种物品同时超过的方案会被减去计算两次，加上即可
同理，减去三种物品同时超过的方案，加上四种物品同时超过的方案，我们就得到了我们要求的东西。

综上，我们得到了一个(O(2^k imes s+2^{2k} imes tot))((k)代表物品数量)的算法，
可以通过本题。

多重背包(娱乐向)的代码

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e9+7;
const int N=3010;
const dd pi=acos(-1);
const int inf=2147483647;
il ll read(){
	RG ll data=0,w=1;RG char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
	return data*w;
}

il void file(){
	srand(time(NULL)+rand());
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
}

ll c[5],d[5],f[100010];
queue<ll>Q;
il ll DP(ll V){
	memset(f,0,sizeof(f));f[0]=1;
	for(RG int i=1;i<=4;i++){
		RG ll sum,ret;
		for(RG ll j=0;j<c[i];j++){
			sum=0;while(!Q.empty())Q.pop();
			for(RG ll k=0;k<d[i]&&(V-j)/c[i]*c[i]+j-k*c[i]>=0;k++){
				Q.push((V-j)/c[i]*c[i]+j-k*c[i]);
				sum+=f[(V-j)/c[i]*c[i]+j-k*c[i]];
			}
			for(RG ll k=(V-j)/c[i]*c[i]+j;k>=0;k-=c[i]){
				ret=f[k];
				if(k-c[i]*d[i]>=0){Q.push(k-c[i]*d[i]);sum+=f[k-c[i]*d[i]];}
				f[k]=sum;sum-=ret;Q.pop();
			}
		}
	}
	return f[V];
}

int main()
{
	RG ll T,s;
	for(RG int i=1;i<=4;i++)c[i]=read();T=read();
	while(T--){
		for(RG int i=1;i<=4;i++)d[i]=read();s=read();
		printf("%lld
",DP(s));
	}
	return 0;
}

(AC)代码

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e9+7;
const int N=3010;
const dd pi=acos(-1);
const int inf=2147483647;
il ll read(){
    RG ll data=0,w=1;RG char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
    return data*w;
}

il void file(){
    srand(time(NULL)+rand());
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
}

ll c[5],d[5];
ll f[16][100010];

il void update(ll &a,ll b){a+=b;}
il void init(){
    memset(f,0,sizeof(f));f[0][0]=1;
    for(RG int i=1;i<=4;i++)
        for(RG int v=0;v+c[i]<=100000;v++)
            for(RG int s=0;s<(1<<4);s++)
                update(f[s|(1<<(i-1))][v+c[i]],f[s][v]);
}

il ll DP(ll V){
    RG ll now,cnt,sum=0;
    for(RG int i=0;i<(1<<4);i++){
        now=V;cnt=0;
        for(RG int j=1;j<=4;j++)
            if(i&(1<<(j-1)))cnt++,now-=c[j]*d[j];
        if(now<0)continue;
        for(RG int j=0;j<(1<<4);j++)
            if((i&j)==i){
                if(cnt&1)sum-=f[j][now];
                else sum+=f[j][now];
            }
    }
    return sum;
}

int main()
{
    RG ll T,s;
    for(RG int i=1;i<=4;i++)
        c[i]=read();
    init();
    
    T=read();
    while(T--){
        for(RG int i=1;i<=4;i++)
            d[i]=read();
        s=read();
        printf("%lld
",DP(s));
    }
    return 0;
}