自动搬运

查看原文

来自洛谷，原作者为

	ScaredQiu Life Still Left In Me

搬运于2025-08-24 23:01:41，当前版本为作者最后更新于2024-02-25 22:40:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

数学、位运算

呼和浩特的小 R 是 RyanLi，另外 shinzanmono 也住在呼和浩特。

---

题目等价于询问是否存在正整数 $x$ 使得 $m$ 个 $x$ 的异或和为 $n$。

测试点 $1 \sim 2$

此时只有 $n=0$。

观察发现当 $m$ 为奇数时无法得到 $0$，$m$ 为偶数时任意 $m$ 个相同正整数异或得到的结果都是 $0$。

• 当 $m$ 为偶数时输出 Yes，否则输出 No。

测试点 $3 \sim 4$

此时只有 $m=2$ 和 $m=3$。

考虑 $m=2$ 的情况，对于任意正整数 $x$，由于 $x$ 和 $x$ 的每个二进制位都相同，所以 $x \oplus x=0$。因而能得到的整数只有 $0$。

考虑 $m=3$ 的情况，由于 $x \oplus x \oplus x=0 \oplus x=x$。故可以得到任意正整数，只有 $0$ 无法被得到。

• 当 $m=2$ 时，若 $n=0$ 输出 Yes，否则输出 No。
• 当 $m=3$ 时，若 $n \neq 0$ 输出 Yes，否则输出 No。

测试点 $5$

因为 $x \oplus x=0$，$x \oplus 0=x$ 且 $m \geq 2$，所以当 $m > 3$ 时 $m$ 个相同正整数的异或等于 $m-2$ 个相同正整数的异或。

$$\underbrace{x \oplus x \oplus x \oplus \cdots \oplus x}_{m\ 个\ x} = 0 \oplus \underbrace{x \oplus \cdots \oplus x}_{m-2\ 个\ x} = \underbrace{x \oplus \cdots \oplus x}_{m-2\ 个\ x} $$

更进一步地，当 $m$ 为奇数时 $m$ 个 $x$ 的异或等于 $3$ 个 $x$ 的异或；当 $m$ 为偶数时 $m$ 个 $x$ 的异或等于 $2$ 个 $x$ 的异或，即 $0$。因此：

• 当 $m$ 为偶数且 $n=0$，输出 Yes。
• 当 $m$ 为奇数且 $n \neq 0$，输出 Yes。
• 其余情况输出 No。

单组数据时间复杂度 $O(1)$。

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(m%2==0&&n==0||m%2==1&&n!=0) puts("Yes");
        else puts("No");
    }
    return 0;
}