题解：P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova
Targanzqq
·
·
题解
不难发现第 2 次操作至多进行 1 次，因为在进行了
然后我们考虑 $1$ 操作的本质：考虑其补集，进行一次 $1$ 操作相当于枚举子集，因此我们只要算出来 $x$ 和 $y$ 补集在 $p$ 补集的子集中的顺序然后相减再加 $1$ 就可以了，而计算顺序也很简单，对二进制拆分后的每个 $2^n$ 找一下子集中比自己小的数然后加起来就可以。时间复杂度 $O(T\log n)$。（还有就是，这题怎么评上蓝的？）
```cpp
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF (1ull<<63)-1
#define bp __builtin_popcountll
using namespace std;
int t,x,y,p,maxn=INF;
signed main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>x>>y>>p;
if(x==y){
cout<<0<<"\n";continue;
}
if((x|(p+1))==y||((x+1)|p)==y){
cout<<1<<"\n";continue;
}
int num=1,nxt=(x|(p+1));
if(nxt>((x+1)|p)&&(nxt&p)==p&&nxt<=y)x=nxt;
else x=(x+1)|p;
if(x==y){
cout<<1<<"\n";continue;
}
if(y<x||(y&p)!=p){
cout<<-1<<"\n";continue;
}
int nx=(maxn^x),ny=(maxn^y);p=(maxn^p);
int ax=0,ay=0;
for(int i=0;i<=62;i++){
if(nx&(1ll<<i)){
int k=((1ull<<i)-1)&p;
ax+=(1ull<<bp(k));
//cout<<k<<" "<<bp(k)<<" "<<ax<<"\n";
}
}
for(int i=0;i<=62;i++){
if(ny&(1ll<<i)){
int k=((1ull<<i)-1)&p;
ay+=(1ull<<bp(k));
//cout<<k<<" "<<ay<<"\n";
}
}
//cout<<ax<<" "<<ay<<" ";
cout<<ax-ay+1ll<<"\n";
}
}