P7076 [CSP-S 2020] Zoo

The zoo keeps many animals. Zookeeper A will buy different types of feed according to the animals being kept, following the “Feeding Guide”, and will send the purchase list to buyer B. Specifically, there are $2^k$ different kinds of animals in the animal world, numbered from $0$ to $2^k - 1$. The zoo keeps $n$ of them, and the ID of the $i$-th animal is $a_i$. There are $m$ rules in the “Feeding Guide”. The $j$-th rule is of the form: “If the zoo keeps some animal such that the $p_j$-th bit of its binary representation is $1$, then it must buy the $q_j$-th type of feed.” There are $c$ types of feed in total, numbered from $1$ to $c$. In this problem, we treat an animal ID’s binary representation as a $k$-bit 01 string: bit $0$ is the lowest bit, and bit $k - 1$ is the highest bit. According to the “Feeding Guide”, A will make a feed list and hand it to B, who will buy the feed. The list is a $c$-bit 01 string: if the $i$-th bit is $1$, it means the $i$-th type of feed needs to be bought; if the $i$-th bit is $0$, it means it does not need to be bought. In fact, based on the feed that has been bought, the zoo may be able to keep more animals. More specifically, if adding a currently unkept animal with ID $x$ to the zoo does not change the feed list, then we say that the zoo can currently also keep the animal with ID $x$. Now B wants you to help compute how many kinds of animals the zoo can still keep at the moment.

The first line contains four integers $n, m, c, k$ separated by spaces. They represent the number of animals currently kept in the zoo, the number of rules in the “Feeding Guide”, the number of feed types, and the number of bits in the binary representation of an animal ID. The second line contains $n$ integers separated by spaces, where the $i$-th integer is $a_i$. The next $m$ lines each contain two integers $p_i, q_i$, describing one rule. The data guarantees that all $a_i$ are pairwise distinct, and all $q_i$ are pairwise distinct.

Output one integer in a single line, representing the answer.

**[Sample #1 Explanation]** The zoo keeps three kinds of animals with IDs $1, 4, 6$. The “Feeding Guide” contains three rules: 1. If some kept animal has the $0$-th binary bit equal to $1$, then feed type $3$ must be bought. 2. If some kept animal has the $2$-th binary bit equal to $1$, then feed type $4$ must be bought. 3. If some kept animal has the $2$-th binary bit equal to $1$, then feed type $5$ must be bought. The feed purchase situation is: 1. The animal with ID $1$ has the $0$-th binary bit equal to $1$, so feed type $3$ needs to be bought. 2. The animals with IDs $4, 6$ have the $2$-th binary bit equal to $1$, so feed types $4, 5$ need to be bought. Since adding an animal with ID being one of $0, 2, 3, 5, 7, 8, \ldots , 15$ will not change the shopping list, the answer is $13$. **[Constraints]** For $20\%$ of the testdata, $k \le n \le 5$, $m \le 10$, $c \le 10$, and all $p_i$ are pairwise distinct. For $40\%$ of the testdata, $n \le 15$, $k \le 20$, $m \le 20$, $c \le 20$. For $60\%$ of the testdata, $n \le 30$, $k \le 30$, $m \le 1000$. For $100\%$ of the testdata, $0 \le n, m \le 10^6$, $0 \le k \le 64$, $1 \le c \le 10^8$. Translated by ChatGPT 5