代码：

#include <bits/stdc++.h>
using namespace std;

int check(int ai){ //这个我是检测哪一位是1的范围是0~k-1
    int k=ai;
    int i=0;
    while (k){
        if (k&1){
            return i;
        }
        k>>=1;
        i++;
    }
    return -1; //没用到但是
}

int a[1000050];
int p[70];

int main(){
    memset(p,0,sizeof(p));
    int n,m,c,k;
    cin>>n>>m>>c>>k;
    for (int i=1;i<=n;i++){ //输入ai
        cin>>a[i];
    }
    int pi,qi;
    for (int i=1;i<=m;i++){ //qi感觉用不到啊
        cin>>pi>>qi;
        p[pi]=1;
    }
    int sum=1; //应为要乘2所以初始设为1
    for (int i=1;i<=n;i++){ //枚举每个动物
        int u=a[i];
        while (u){ //如果u即ai的二进制还有数的话
            if (p[check(u)]==1)//把在指南里的且在动物的二进制表示里的数标记成2
                p[check(u)]=2;
            u-=u&-u;//把检测过的位数的1删掉
        }
    }
    for (int i=0;i<k;i++){
        if (p[i]==2||p[i]==0){ //2表示饲料买了所以可以算，0表示根本不在指南上可以算
            // cout<<i<<endl; //不用管 测试用的
            sum*=2; //每次乘2
        }
    }
    sum-=n; //把动物数减掉防止重复
    if (sum<0) { //没用上
        cout<<0;
    }
    else 
        cout<<sum;
    return 0;
}