思路

优化1：求每个数的第几位为1，所以可以将所有动物编号或起来
优化2：因为qi互不相同，不同的饲料最多有k=64种

如果买了这一位饲料，因为买了不一定需要吃，所以可填0也可填1，有两种选择
如果一位没有饲料，同时也没出现在要求当中，同样有两种选择
如果一位没有饲料，但在要求中，不可饲养，只能填0

细节处理：因为k最大是64位，所以需要无符号位的long long类型

时间复杂度

O(n)

参考文献

y总讲解视频（目移

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=64;

int n,m,c,k;
bool has_[N];//每一位是否被要求过
bool food_[N];//是否买了这一类饲料，最多64类

int main(){
    scanf("%d%d%d%d",&n,&m,&c,&k);
    ull sta=0;
    for(int i=0;i<n;i++){
        ull x;
        scanf("%llu",&x);//此处输入类型注意 
        sta|=x;
    }

    for(int i=0;i<m;i++){
        int p,q;
        scanf("%d%d",&p,&q);
        has_[p]=true;//第p位有要求
        if(sta>>p&1) food_[p]=true;//需要第p类饲料
    }

    int cnt=0;//计算多少类有两种选择
    for(int i=0;i<k;i++){
        if(food_[i]||!has_[i]) cnt++;
    }

    if(cnt==64&&!n) puts("18446744073709551616");//long long无符号位最多存2^64-1，所以直接输出2^64值
    else if(cnt==64){
        ull t=-1;//补码:2^64-1
         printf("%llu\n",t-(n-1));//2^64
    }
        else printf("%llu\n",(1ull<<cnt)-n);

    return 0;
}