Luogu

BZOJ

分析

首先算出没有限制的方案数,这个和今年D1T2差不多,跑遍完全背包就行。

然后用容斥去做,减掉有一种超出的,加上有两种超出的,再减掉用三种超出的,最后加上四种都超出的。

正确性是显然的。当然要判有没有这种情况。

一开始可以$O(400000)$预处理出无限制的方案数。

代码

打表是OI的一部分,不爽不要看

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXS=100000+10;
int f[MAXS];
int c[10],d[10];

inline int g(int x) { return c[x]*(d[x]+1); }

mainint main() {
    for (re int i=1;i<=4;++i) c[i]=read();
    f[0]=1;
    for (re int i=1;i<=4;++i)
        for (re int j=c[i];j<=1e5;++j)
            f[j]+=f[j-c[i]];
    int T=read();
    while (T--) {
        for (re int i=1;i<=4;++i) d[i]=read();
        int S=read(),ans=f[S];
        //不会位运算
        if (S>=g(1)) ans-=f[S-g(1)];
        if (S>=g(2)) ans-=f[S-g(2)];
        if (S>=g(3)) ans-=f[S-g(3)];
        if (S>=g(4)) ans-=f[S-g(4)];
        if (S>=g(1)+g(2)) ans+=f[S-g(1)-g(2)];
        if (S>=g(1)+g(3)) ans+=f[S-g(1)-g(3)];
        if (S>=g(1)+g(4)) ans+=f[S-g(1)-g(4)];
        if (S>=g(2)+g(3)) ans+=f[S-g(2)-g(3)];
        if (S>=g(2)+g(4)) ans+=f[S-g(2)-g(4)];
        if (S>=g(3)+g(4)) ans+=f[S-g(3)-g(4)];
        if (S>=g(1)+g(2)+g(3)) ans-=f[S-g(1)-g(2)-g(3)];
        if (S>=g(1)+g(2)+g(4)) ans-=f[S-g(1)-g(2)-g(4)];
        if (S>=g(1)+g(3)+g(4)) ans-=f[S-g(1)-g(3)-g(4)];
        if (S>=g(2)+g(3)+g(4)) ans-=f[S-g(2)-g(3)-g(4)];
        if (S>=g(1)+g(2)+g(3)+g(4)) ans+=f[S-g(1)-g(2)-g(3)-g(4)];
        printf("%lld\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 39 PM