思路与算法

现有动物编号按位或确定哪些要求已触发。带饲料规则却从未出现1的位必须保持0，其余位自由；方案数为2的自由位数次方减已有动物数，128位承接2^64。

正确性说明

同一位出现1会触发该位的所有不同饲料要求，而q互异确保未触发规则不能被别的位同名饲料代替。因此新增动物正好不能在受限位写1，自由位独立二选一。现有每种动物均在合法集合内且互不相同，减n得可新增数量。

复杂度

O(n+m+k)时间、O(64)额外空间，流式读动物与规则；128位输出递归深度为常数上限20位。

易错点

k=64时不能用64位的1左移64；空动物园及k=0同样合法，动物编号用无符号64位读入。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
void print(__uint128_t v) {
    if (v >= 10)
        print(v / 10);
    cout << char('0' + v % 10);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, c, k;
    cin >> n >> m >> c >> k;
    unsigned long long all = 0;
    for (int i = 0; i < n; i++) {
        unsigned long long a;
        cin >> a;
        all |= a;
    }
    bool required[64] = {};
    for (int i = 0; i < m; i++) {
        int p, q;
        cin >> p >> q;
        required[p] = 1;
    }
    int free = k;
    for (int p = 0; p < k; p++)
        if (required[p] && !(all >> p & 1ULL))
            free--;
    print(((__uint128_t)1 << free) - n);
    cout << "\n";
}