或与异或

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给出两个数a , b a,ba,b，可以对其进行无限次操作，每次操作可以选择a aa和b bb其中一个数作为操作对象，然后将操作对象的值变成以下三种之一，另一个不变：

• 1)a ∣ b a∣ba∣b。(按位或运算符“ ∣ ” “|”“∣”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1 11时，结果位就为1 11。)

• 2)a & b a\&ba&b。(按位与运算符“ & ” “\&”“&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为1 11时，结果位才为1 11。)

• 3. a ⊕ b a⊕ba⊕b。(按位异或运算符“ ˆ ” “ \^\ ”“ˆ”是双目运算符。其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1 11。)

对于每组给出的a aa和b bb，给出一个t a r g e t targettarget，判断是否可以通过操作使得a aa和b bb其中之一变成t a r g e t targettarget。

输入描述：

第一行包含一个整数T ( 1 ≤ T ≤ 10 4 ) T (1≤T≤10^4)T(1≤T≤104)，表示T TT组询问。

接下来T TT行，每行包含三个整数a b t a r g e t ( 0 ≤ a , b , t a r g e t ≤ 10 17 ) a \ b \ target (0≤a,b,target≤10^{17})abtarget(0≤a,b,target≤1017)。

输出描述：

输出包含T TT行，对于每个询问，如果a aa和b bb能通过操作得到t a r g e t targettarget， 输出YES，否则输出NO。

示例1

输入：

3 1 2 3 3 2 4 3 5 3

输出：

YES NO YES

说明：

1 ⊕ 2 = 3 1⊕2=31⊕2=3，输出Y E S YESYES。
对于a = 3 , b = 2 a=3,b=2a=3,b=2，不存在任意操作组合可以使得其中之一变成4 44，输出N O NONO。
无需操作，初始时a = t a r g e t a=targeta=target，输出Y E S YESYES。

解题思路

本题是位运算性质推导题，核心是利用位运算的逐位独立性，将二进制位分类并分析绑定关系，最终将可达性判定转化为集合覆盖校验，实现每组查询O(1)的高效求解。

1. 位分类与绑定性质

按位与、或、异或运算均不产生进位，每一位的运算结果仅由两个数的对应位决定。我们将所有二进制位按a、b的取值分为三类：

• 双1位x = a & b：a和b对应位均为1
• 仅b为1位y = (~a) & b：a对应位为0，b对应位为1
• 仅a为1位z = a & (~b)：a对应位为1，b对应位为0

由于同一类的所有位在a、b中的取值完全一致，每次位运算对同类别位的修改是同步的：要么全部变为1，要么全部变为0。因此每一类位是不可拆分的整体，只能整体保留或整体去除，无法单独选中某一类中的部分位。

2. 可达性判定结论

通过任意次操作能得到的数，恰好是上述三类位的任意子集的并集（每一类要么全选，要么全不选）。因此target可达的充要条件是：

target的所有1位可以被若干个完整的类别覆盖，即对每一类，target要么包含该类的全部位，要么不包含该类的任何位。

同时，a、b均为0的位永远无法生成1，若target在这类位上为1则直接不可达，该逻辑已被上述校验条件自然覆盖。

3. 校验方法

依次校验三类位：

• 若某类的所有位在target中均为1，说明该类被完整选中，将该类的所有位从target中移除。
• 若某类部分位在target中为1、部分为0，说明无法拆分该类，target不可达。

最终若target被完全清空（所有1位都被完整类覆盖），则可达，否则不可达。

算法每组查询时间复杂度为O(1)，可轻松应对1万组测试数据。

总结

核心逻辑：将二进制位按初始取值分为三类，利用位运算的同步性得出每类不可拆分的结论，通过校验target是否为若干完整类的并集来判定可达性。
关键操作：三类位掩码计算、逐类完整覆盖校验、剩余位清零判定。
效率保障：单组查询仅需常数次位运算，万级数据毫秒级完成。

代码简要说明

1. 位分类计算：通过位运算计算三类位的掩码x、y、z，分别对应双1位、仅b为1位、仅a为1位。
2. 逐类校验移除：依次检查每一类，若该类的所有位都在target中（x & (~c) == 0），则将该类位从target中清除（c &= ~x）。
3. 结果判定：最终若c为0，说明target可由若干完整类组合得到，输出YES；否则输出NO。
4. 输入优化：关闭流同步加速输入输出，适配万级测试用例的读取效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cin>>T;while(T--){ll a,b,c;cin>>a>>b>>c;ll x,y,z;x=a&b;y=(~a)&b;z=a&(~b);if(!(x&(~c)))c&=~x;if(!(y&(~c)))c&=~y;if(!(z&(~c)))c&=~z;if(c)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}return0;}