题目都看得懂,我们先谈dp再谈容斥。

dp的思想就是,先假设每个硬币都不限制数量(给出一个最大界限数量即可),然后统计他们能组成的付款方法有多少种。状态转移方程为:

dp[j] = dp[j] + dp[j-c[i]]

意思就是,组成当前j元付款方法的方式数是在j原有的方法上加上一个 不加当前硬币的方法数。(有点绕口,自己想想就明白了。)

然后接下来理解容斥。

这里的容斥方法是先假设每种硬币的数量都超出了给定的数目。

我们用没有限制硬币数量的方法数,减去超出限制的方案数,即可得到需要的方案数了。

然后,超出的方案怎么计算呢?公式是:

f[s-(d[i]+1)*c[i]] ,就是当前方案数减去刚好超过的方案数,即可得到超出的方案数(取得是刚好超过到当前ans中间的部分,自行体会)。

但是这样减会出问题,因为我们会减掉重合的部分。所以来看容斥:

设A为第一个硬币超限的方案数,B为第二个硬币超限的方案数,C为第三个硬币超限的方案数,D为第四个硬币超限的方案数。

那么:

AUBUCUD=A+B+C+D-A∩B-B∩C-A∩C-A∩D-B∩C-B∩D-C∩D+A∩B∩C+A∩B∩D+A∩C∩D+B∩C∩D-A∩B∩C∩D;

那么,我们用总的数目-超限方案数(AUBUCUD)即可得到正确的答案。


下面附上一张盗来的图,请仔细欣赏!!!



代码:

StatusAccepted
Time40ms
Memory2068kB
Length1205
LangC++


#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
#define MAX 100005
#define LL long long
int c[5], d[5], tot, s;
LL f[MAX];
LL ans;
int main()
{
    for(int i=1; i<5; i++)scanf("%d",&c[i]);
    scanf("%d", &tot);
    f[0]=1;
    for(int i=1; i<5; i++)
    {
        for(int j=c[i]; j<100001; j++)
        {
            f[j]+=f[j-c[i]];
        }
    }
    while(tot--)
    {
        for(int i=1; i<5; i++)scanf("%d", &d[i]);
        scanf("%d", &s);
        ans=f[s];
        for(int i=1; i<5; i++)
        {
            if(s>=(d[i]+1)*c[i])ans-=f[s-(d[i]+1)*c[i]];
        }
        for(int i=1; i<4; i++)for(int j=i+1; j<5; j++)
            {
                if(s>=(d[i]+1)*c[i]+(d[j]+1)*c[j])ans+=f[s-(d[i]+1)*c[i]-(d[j]+1)*c[j]];
            }
        for(int i=1; i<3; i++)for(int j=i+1; j<4; j++)for(int k=j+1; k<5; k++)
                {
                    if(s>=(d[i]+1)*c[i]+(d[j]+1)*c[j]+(d[k]+1)*c[k])ans-=f[s-(d[i]+1)*c[i]-(d[j]+1)*c[j]-(d[k]+1)*c[k]];
                }
        if(s>=(d[1]+1)*c[1]+(d[2]+1)*c[2]+(d[3]+1)*c[3]+(d[4]+1)*c[4])ans+=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];
        printf("%lld\n", ans);
    }
    return 0;
}