『FLA - I』冲云霄

ScaredQiu · 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 个相同正整数的异或。

更进一步地，当 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;
}