G31 容斥原理 集合的交

G31 容斥原理 集合的交

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
int c[4],d[4],n,s;
LL f[100005];

void pack_pre(){ //完全背包预处理
    f[0] = 1;
    for(int i=0; i<4; i++)
      for(int j=c[i]; j<100005; j++)
        f[j] += f[j-c[i]];
}
LL calc(LL s){ //容斥原理
  LL res = 0;
  for(int i=1; i<1<<4; i++){//枚举状态
    LL t = 0, sign = -1;
    for(int j=0; j<4; j++) //过滤状态
      if(i & 1<<j){
        t += c[j]*(d[j]+1);
        sign = -sign;      
      }
    if(s>=t) res += f[s-t]*sign;
  }
  return f[s]-res;
}
int main(){
    for(int i=0; i<4; i++) scanf("%d",&c[i]);
    pack_pre(); 
    scanf("%d", &n);
    while(n--){
        for(int i=0; i<4; i++) scanf("%d",&d[i]);
        scanf("%d",&s);
        printf("%lld\n", calc(s));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5;
int c[5],d[5];
LL f[110000];
int main()
{
    for(int i=1;i<=4;i++)scanf("%d",&c[i]);
    memset(f,0,sizeof(f));f[0]=1;
    for(int i=1;i<=4;i++)
    	for(int j=c[i];j<=N;j++)
    		f[j]+=f[j-c[i]];
    int T;scanf("%d",&T);
    while(T--)
    {
    	for(int i=1;i<=4;i++)scanf("%d",&d[i]);
    	int s;scanf("%d",&s);
    	LL ans=f[s];
    	for(int i=1;i<16;i++) //枚举所有16种状态(2^4-1)
    	{
    		LL ss=s,sign=1;
    		for(int j=1;j<=4;j++) //检查每个物品是否被选中
    		{
    			if(i&(1<<(j-1))) //如果选中，减去该物品的最大允许贡献
    			{
    				ss-=c[j]*(d[j]+1);
    				sign*=-1; //容斥原理符号翻转
    			}
    		}
    		if(ss<0) continue; //贡献为负，跳过
    		ans+= f[ss]*sign; //累加贡献
    	}
	    printf("%lld\n",ans);
    }
    return 0;
}