[CSP‑S 2020] 动物园] 题解

（看前警告：这是一篇超详细+超麻烦的代码，能自己写的不要看，应该没你的方法好。）

题意简述

总共有 $2^k$ 种动物，编号 $0 \sim 2^k-1$。
有 $m$ 条规则：只要动物园里面存在动物编号第 $p$ 位为 $1$，就必须购买饲料 $q$。现在已经养了 $n$ 只动物，饲料清单已经确定。
一只新动物 $x$ 可以被添加的条件：加入 $x$ 不会增加任何需要买的饲料。
求还可以新增多少种动物。

思路分析

have_ bit[p]：现有的动物中是否存在某只动物二进制第 $p$ 位是 $1$
has_rule[p]：第 $p$ 位有没有绑定饲料（该位为 $1$ 需要买饲料）
一个二进制位 $p$ 是自由位，满足下面任意一条即可：
该位没有饲料约束，可以随便填 $0/1$
该位虽然有饲料约束，但是已经被现有动物激活 $have_bit[p]=true$，新动物这一位填 $1$ 也不会多出饲料
合法动物总数量：$2^{\text{自由位个数}}$
答案 = 合法总数 − 当前已经有的动物 $n$

坑点详解

$k$ 最大等于 $64$，$2^{64}$ 超出 unsigned long long 的范围

$free_bit = 64$ 并且 $n=0$：直接输出字符串 18446744073709551616
$free_bit = 64$ 并且 $n>0$：使用 ULLONG_MAX - n + 1
动物编号最大可以是 $2^{64}-1$，读入变量必须用 unsigned long long
$n,m \le 10^6$，一定要开输入加速，否则超时
（ 当然了，我自己都没写）
复杂度 $O(nk+m+k)$，$k \le 64$

读到这先别看了，自己再去看看题，写一写吧

肥美无敌代码展示

你应该也不需要了吧

（终于会用 $美元符号写题解了$ hhh 写这种变量名的代码在我的写的题里面不多见（ $保持神秘$））

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
const int MAXN=1000005;
int a[MAXN];
bool have_bit[65]={false};
bool has_rule[65]={false};
ull pow2(int x){
    if(x==64){
        return 0;
    }
    return 1ULL<<x;
}
void solveA(){
    int n,m,c,k;
    cin>>n>>m>>c>>k;
    for(int i=0;i<n;i++){
        ull num;
        cin>>num;
        for(int p=0;p<k;p++){
            if((num>>p)&1){
                have_bit[p]=true;
            }
        }
    }
    while(m--){
        int p,q;
        cin>>p>>q;
        has_rule[p]=true;
    }
    int free_bit=0;
    for(int p=0;p<k;p++){
        if(!has_rule[p]){
            free_bit++;
        }
        else{
            if(have_bit[p]){
                free_bit++;
            }
        }
    }
    if(free_bit==64){
        if(n==0){
            cout<<"18446744073709551616";
        }
        else{
            cout<<(ULLONG_MAX-n+1);
        }
        return;
    }
    ull total=pow2(free_bit);
    ull ans=total-n;
    cout<<ans;
}
int main(){
    solveA();
}