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

· · 题解

前记： 我在做这道题的时候已经被T1卡了两个半小时，在此重新感谢儒略日出题人。

翻译一下题面，大概就是：一共有从0到k-1一共k位，每一位都有不同的要求，现在给你一些数字，这些数字对应的二进制位上的要求都是已经满足的，求不增加其他要求的情况下，可以选择的数字种类。

我们首先需要找出所有的已有的位，这里我用一个64位的unsigned long long变量的每一位去记录。

 for(int i=1;i<=n;i++)
    {
        scanf("%llu",&x);
        cnt=cnt|x;
    }

然后我们去记录有要求的位 因为所有的q都不相同，我们完全没必要记录下来所有的q，只需要记录最后一个以标志这一位是有要求的就可以

for(int i=1;i<=m;i++)
    {
        int p,q;
        scanf("%d%d",&p,&q);
        s[p]=q;
    }

然后我们再去找有哪些位的要求是我们可以满足的。

for(int i=0;i<64;i++)
        if((cnt&(1ll<<i))&&s[i])
            s[i]=0;

这样我们就有了那些有要求但是无法满足的位的数目

for(int i=0;i<64;i++)
    if(s[i])    qwq++;

在这些位里面，只要有1位是1，那么对应数字我们都不能要。

一共是qwq位数字，共2^{qwq}种不同的情况，全是0的只有一种，那么这些位上不同的组合有2^{qwq}-1种

剩余位置随便什么数字都可以，那么一共有2^{k-qwq}种组合，乘起来就是我们不能要的数字的数目。

    ans=1ll<<(k-1);
    ans-=n;
    ans+=(1ll<<(k-1));
    ans-=((1ll<<qwq)-1)*(1ll<<(k-qwq));

再加上一个满怀恶意的特判，比T1简单许多的T2的100分就到手啦！（虽然我考场上并没有AC）

if(n==0&&m==0&&k==64)
    {
        printf("18446744073709551616");
        return 0;
    }

完整代码

#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long 
using namespace std;
ull n,m,c,k;
ull x;
ull cnt;
ull qwq;
int s[70];
ull ans;
int main()
{
    scanf("%llu%llu%llu%llu",&n,&m,&c,&k);
    if(n==0&&m==0&&k==64)
    {
        printf("18446744073709551616");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%llu",&x);
        cnt=cnt|x;
    }
    for(int i=1;i<=m;i++)
    {
        int p,q;
        scanf("%d%d",&p,&q);
        s[p]=q;
    }
    for(int i=0;i<64;i++)
        if((cnt&(1ll<<i))&&s[i])
            s[i]=0; 
    for(int i=0;i<64;i++)
    if(s[i])    qwq++;
    ans=1ll<<(k-1);
    ans-=n;
    ans+=(1ll<<(k-1));
    ans-=((1ll<<qwq)-1)*(1ll<<(k-qwq));
    printf("%llu",ans);
    return 0;
}