40pts

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    int n, m, c, k;
    cin >> n >> m >> c >> k;
    
    vector<long long> animals(n);
    for (int i = 0; i < n; i++) {
        cin >> animals[i];
    }
    
    vector<int> p(m), q(m);
    for (int i = 0; i < m; i++) {
        cin >> p[i] >> q[i];
    }
    
    // 计算当前需要的饲料
    vector<bool> need(c + 1, false);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((animals[i] >> p[j]) & 1) {
                need[q[j]] = true;
            }
        }
    }
    
    // 用 unordered_set 存储已有动物，方便快速查找
    unordered_set<long long> exist;
    for (int i = 0; i < n; i++) {
        exist.insert(animals[i]);
    }
    
    int ans = 0;
    long long total = 1LL << k;  // 2^k 种动物
    
    // 枚举所有可能的动物编号
    for (long long x = 0; x < total; x++) {
        // 如果已经在动物园中，跳过
        if (exist.count(x)) continue;
        
        bool ok = true;
        // 检查加入 x 后是否会改变饲料清单
        for (int j = 0; j < m; j++) {
            if ((x >> p[j]) & 1) {
                // 如果该位为1，但对应的饲料还没购买，则清单会变化
                if (!need[q[j]]) {
                    ok = false;
                    break;
                }
            }
        }
        
        if (ok) ans++;
    }
    
    cout << ans << endl;
    return 0;
}

100pts

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

bool has[N];//表示每一位有没有被要求过
bool food[N];//表示是否买了这一类的饲料
int main()
{
	int n,m,c,k;
	scanf("%d%d%d%d",&n,&m,&c,&k);	
	ULL state=0;
	for(int i=1;i<=n;i++)
	{
		ULL x;
		scanf("%llu",&x);
		state|=x;
	}
	//state就是所有动物的异或值
	for(int i=1;i<=m;i++) 
	{
		int p,q;
		scanf("%d%d",&p,&q);
		has[p]=true;//p位有要求
		if(state>>p&1) //有某个动物的pj位为1，说明qj一定要买 
		{
			food[p]=1;//p为1这一类一定要买 
		} 
	}
	int cnt=0;
	for(int i=0;i<k;i++) //依次枚举每类饲料 
	{
		if(food[i]||!has[i]) //当前这个饲料有或者是当前这个饲料没有(但是没有要求) 
		{
			cnt++;
		}
	}
	if(cnt==64&&!n)
	{
		cout<<"18446744073709551616";
	}
	else if(cnt==64)
	{
		ULL t=-1;//2^64-1;
		cout<<t-(n-1);
	}
	else
	{
		cout<<(1ull<<cnt)-n;
	}
	return 0;
}