题目描述

动物园里饲养了很多动物，饲养员小 A
会根据饲养动物的情况，按照《饲养指南》购买不同种类的饲料，并将购买清单发给采购员小 B
。

具体而言，动物世界里存在 2k
种不同的动物，它们被编号为 0∼2k−1
。

动物园里饲养了其中的 n
种，其中第 i
种动物的编号为 ai
。

《饲养指南》中共有 m
条要求，第 j
条要求形如“如果动物园中饲养着某种动物，满足其编号的二进制表示的第 pj
位为 1
，则必须购买第 qj
种饲料”。

其中饲料共有 c
种，它们从 1∼c
编号。

本题中我们将动物编号的二进制表示视为一个 k
位 01
串，第 0
位是最低位，第 k−1
位是最高位。

根据《饲养指南》，小 A
将会制定饲料清单交给小 B
，由小 B
购买饲料。

清单形如一个 c
位 01
串，第 i
位为 1
时，表示需要购买第 i
种饲料；第 i
位为 0
时，表示不需要购买第 i
种饲料。

实际上根据购买到的饲料，动物园可能可以饲养更多的动物。

更具体地，如果将当前未被饲养的编号为 x
的动物加入动物园饲养后，饲料清单没有变化，那么我们认为动物园当前还能饲养编号为 x
的动物。

现在小 B
想请你帮忙算算，动物园目前还能饲养多少种动物。

输入格式
第一行包含四个以空格分隔的整数 n、m、c、k
。分别表示动物园中动物数量、《饲养指南》要求数、饲料种数与动物编号的二进制表示位数。

第二行 n
个以空格分隔的整数，其中第 i
个整数表示 ai
。

接下来 m
行，每行两个整数 pi,qi
表示一条要求。

数据保证所有 ai
互不相同，所有的 qi
互不相同。

输出格式
仅一行一个整数表示答案。

数据范围
对于 20%
的数据：k≤n≤5,m≤10,c≤10
，所有的 pi
互不相同。
对于 40%
的数据：n≤15,k≤20,m≤20,c≤20
。
对于 60%
的数据：n≤30,k≤30,m≤1000
。
对于 100%
的数据：0≤n,m≤106,0≤k≤64，1≤c≤108,0≤pi<k,1≤qi≤c
。

样例

 3 3 5 4
1 4 6
0 3
2 4
2 5

输出

13

这道题也太会坑了（再次感谢儒略日出题人）
这道题我当时看完直接感觉完了，所以想着就拿部分分（反正做完T1就崩溃了）
我就想这个题的算法可以大胆一些
直接忽略饲料
毕竟是01串也就是二进制
直接看每一位有没有提要求
所以整个状态就分为了两种
1.有要求的
2.没要求的
所以先用动物去满足要求
再用饲料看有没有要求没有被满足
最后就可以出答案（感觉是部分分）了

万万没想到这题这么做能满分！！！

C++ 代码

 #include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
bool fg[65],mfg[65];
int n,m,c,k,cnt;
int main(){
     ios::sync_with_stdio(false);
    cin>>n>>m>>c>>k;
    for(int i=0;i<n;i++){
        ull tmp;
        cin>>tmp;
        for(int j=k-1;j>=0;j--) fg[j] |= (tmp>>j)&1;
    }
    for(int i=0;i<m;i++){
        int p,q;
        cin>>p>>q;
        if(!fg[p]){
            mfg[p]=1;
        }
    }
    for(int i=0;i<k;i++){
        if(mfg[i]) cnt++;
    }
     if (k - cnt == 64) {
    if (n)
      cout << ull(-n) << endl;
    else
      cout << "18446744073709551616" << endl;
  } else
    cout << (1ull << (k - cnt)) - n << endl;

    return 0;
}