【CSP2020】 T3 动物园

题目链接
https://www.luogu.com.cn/problem/P7076?contestId=37022

可以发现给定的(n)种动物的编号完全可以按位或来合并，假设合并后的结果为(sum)。

首先我们扫一遍所有的要求，得到当前动物需要的饲料集合(S)(注意到要求最多只有1e6条，所以(1leq cleq 10^8)完全是唬人的，直接离散化，就可以开数组维护（我不知道开1e8数组会不会炸）。

然后再扫一遍，假设当前的要求是(p_i,q_i)，如果(sum)的(p_i)位为(1)，说明(q_i)已经在(S)中，新加入的动物本位可以取(1)也可以取(0)。

如果(sum)的(p_i)位为(0)，就看(S)中存不存在(q_i)，若存在，那么新加入的动物本位可以取(1)也可以取(0)；否则只能取(0)。

所以再开一个digit数组，保存每一位有几种取法，乘起来，减去已有的(n)，就是最终答案。

开了ull还是炸了，据说要特判，但我比较懒，想100的同学自行完善一下（逃

代码

#include<cstdlib>
#include<algorithm>
#define ull unsigned long long
using namespace std;
int book[1000010],dig[65];
struct query{
	int pos,c,id,c1;
} q[1000010];
bool cmp1(query x,query y){
	return x.c<y.c;
}
bool cmp2(query x,query y){
	return x.id<y.id;
}
int main(){
	int n,m,c,k,i,j,cnt=0;
	ull s=0,x,ans=1;
	// freopen("zoo3.in","r",stdin);
	// freopen("out.txt","w",stdout);
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for(i=1;i<=n;i++){
		scanf("%lld",&x);
		s|=x;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&q[i].pos,&q[i].c);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp1);
	for(i=1;i<=m;i++){
		if(q[i].c>q[i-1].c) cnt++;
		q[i].c1=cnt;
	}
	sort(q+1,q+m+1,cmp2);
	for(i=1;i<=m;i++){
		int t=q[i].pos;
		if(s&((ull)1)<<t) book[q[i].c1]=1;
	}
	for(i=1;i<=m;i++){
		int t=q[i].pos;
		if(!(s&((ull)1)<<t)){
			if(!book[q[i].c1]) dig[t]=1;
		}
	}
	for(i=0;i<k;i++)
		if(!dig[i]) ans<<=1;
	printf("%lld",ans-n);
	// system("pause");
	return 0;
}