P10118 『STA - R4』And 题解

题目

看到位运算，直接二进制拆分考虑。

首先 \(x \operatorname{AND}y=B\)，设 \(x=B+m\)，\(y=B+n\)，知道 \(x+y=A\)，所以设 \(W=n+m=A-2\times B\)，\(y-x\) 等价于 \(n-m\)。

因为已知 \(x\operatorname{AND}y=B\)，所以 \(n\operatorname{AND}m=0\)，着意味着在二进制下 \(n\) 和 \(m\) 不存在某一位上都是 \(1\)，我们将 \(W\) 进行二进制拆分为 \(n\) 和 \(m\)。

设 \(w=\sum\limits_{i=1}^{tot}2^{p_i}\)，它在二进制下一共有 \(tot\) 个 \(1\)，构成集合 \(U\)，考虑如何将这些 \(1\) 分配给 \(n\) 和 \(m\)。

首先从左往右数的第一个 \(1\) 要分配给 \(n\) 保证 \(n>m\)，然后我们设剩下的 \(1\) 分配给 \(n\) 的为集合 \(Sn\)，则分配给 \(m\) 的 \(1\) 构成的集合为 \(\complement_{U}Sn\)，那么此时也必有一种情况为分配给 \(n\) 的为集合 \(\complement_{U}Sn\)，分配给 \(m\) 的为集合 \(Sn\)，两种情况彼此抵消，最后会产生 \(2\times2^{p_1}\) 的贡献，也就是说一种情况只会产生一次 \(2^{p_1}\) 的贡献。

情况总数为 \(2^{popcount(W)-1}\)，答案就是

关于不合法的情况我们在前面已经提到过了，\(n\) 和 \(m\) 必须要满足\(n\operatorname{AND}m=0\)，所以 \(W\operatorname{AND}B=0\)，否则为不合法。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
inline int read(){
    char ch=getchar();int x=0,f=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
signed main(){
    // freopen("in.in","r",stdin),freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    int T=read(),mod=read();
    while(T--){
        int a=read(),b=read();      
        int w=a-2*b;
        if(b&w||w<0){std::cout<<0<<'\n';continue;}
        int tot=__builtin_popcountll(w)-1;tot=(1ll<<tot)%mod;
        int zc=std::__lg(w);w=1ll<<zc;
        std::cout<<w%mod*tot%mod<<'\n';
    } 
}

吐槽一下出题人UU造的数据，你往每一个点里都塞特殊情况是吧，太毒瘤了。