题解 P7076 【动物园（洛谷民间数据）】

· · 题解

众所周知，动物园是不需要动物的

水题中的水题，稍微分析下就能明白此中的逻辑了。

有一个条件是“所有的 q_i 互不相同”，这意味着饲料是啥都不重要了，c 和 q_i 甚至不用读进来。

注意全程要用unsigned long long类型，读入要用%llu。

先计算出所有已有的动物编号中，哪些位至少存在一次，显然用|运算就行了。

对于每个要求，如果第 p_i 位是存在的，那这种饲料就肯定有了。反之这种饲料是一定没有的，也就是说这一位一定不能为 1。

除去一定不能为 1 的位，剩下 t 个位可能为 1，那总动物数就能达到 2^t，减去已经有的 n 个动物，所以答案是 2^t-n。

这里有个坑点：当 t=64 时，如果 n>0 ，那 2^{64} 算出来会等于 0 ，然后自然溢出是没事的。但是！！！这题的 n 居然会等于 0，和题目的第一句话“动物园里饲养了很多动物”显然矛盾。

这时候，只能输出"18446744073709551616”这个字符串了，当然你不需要背下来，只要先输出一个(unsigned long long)-1 再加上 1 就行了。

代码如下，时间复杂度 O(n+m)：

typedef unsigned long long ULL;
int main() {
    int n, m, c, K;
    scanf("%d%d%d%d", &n, &m, &c, &K);
    ULL flag = 0, g = 0;
    for (int i = 0; i < n; i++) {
        ULL x;
        scanf("%llu", &x);
        flag |= x;
    }
    while (m--) {
        int p;
        scanf("%d%*d", &p);
        if ((flag >> p & 1) == 0) g |= 1ULL << p;
    }
    ULL ans = 1;
    for (int i = 0; i < K; i++) {
        if ((g >> i & 1) == 0) ans <<= 1;
    }
    if (ans == 0 && n == 0) {
        puts("18446744073709551616");
        return 0;
    }
    ans -= n;
    printf("%llu\n", ans);
    return 0;
}