P10835 『FLA - I』冲云霄 题解

andycode · 2024-08-03 18:21:48 · 题解

题目传送门

题意概要

给出两个整数 n,m，判断是否存在一个长度为 m 的序列 a，满足以下条件。

• 数列中的元素为正整数。

• 即序列 $a$ 的所有项异或得到的结果等于 $n$。

• 数列 a 中所有元素的值都相同。

  思路讲解

  仔细观察，不难发现 x \oplus x=0(x \in \N)，且 0 \oplus x=x(x \in \N)。根据这两条公式，可得出以下结论。

当 m 为奇数时，a_1 \oplus a_2 \oplus \dots \oplus a_m=a_m(m \bmod 2=1)。因为可以将序列 a 中的所有除了 a_m 以外的元素两两异或为 0（因为序列 a 中的元素都相同，所以根据前面的公式，两两异或后的结果为 0），结果最后就等于 0 \oplus a_m 也就是 a_m。

当 m 为偶数时，a_1 \oplus a_2 \oplus \dots \oplus a_m=0(m \bmod 2=0)。与上面同理，将序列中的元素两两异或为 0，最终结果为 0。

根据上面得出的结论，分类讨论。

当 n=0 时，只有当 m 为偶数时，才存在满足条件的序列 a，因为当 m 为偶数时，a_1 \oplus a_2 \oplus \dots \oplus a_m=0。否则当 m 为奇数时，因为序列 a 中的元素都为正整数，所以根据上面得出的公式(a_1 \oplus a_2 \oplus \dots \oplus a_m=a_m(m \bmod 2=1))，a_1 \oplus a_2 \oplus \dots \oplus a_m 的结果肯定也为一个正整数。

当 n>0 时，只有当 m 为奇数时，才存在满足条件的序列，因为当 m 为奇数时，a_1 \oplus a_2 \oplus \dots \oplus a_m=a_m(m \bmod 2=1)，当序列 a 中的元素为 n 既可。否则当 m 为偶数时，根据上面得出的公式，a_1 \oplus a_2 \oplus \dots \oplus a_m=0(m \bmod 2=0)。不管序列 a 的元素是多少，只要是正整数，结果一定会是 0 。不可能存在结果大于 0 的情况。

代码实现

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(n==0 && m%2==0)cout<<"Yes";
        else if(n==0 && m%2==1)cout<<"No";
        //当n等于0且m为偶数，则存在a数列
        else if(n && m%2==1)cout<<"Yes";
        else cout<<"No";
        //否则当n大于0且m为奇数，则存在a数列
        cout<<endl;
    } 
    return 0;
}

完结撒花！

（该题解为本蒟蒻的第一篇题解，如有可以改进的地方，欢迎大家在评论区指出）