[Codeforces Round #717 (Div. 2)]AGAGA XOOORRR(^(异或)符号的特性)题解

B. AGAGA XOOORRR

time limit per test

1 second

memory limit per test

256 megabytes

题目描述

Baby Ehab is known for his love for a certain operation. He has an array a of length n, and he decided to keep doing the following operation on it:

he picks 2 adjacent elements; he then removes them and places a single integer in their place: their bitwise XOR. Note that the length of the array decreases by one.

Now he asks you if he can make all elements of the array equal. Since babies like to make your life harder, he requires that you leave at least 2 elements remaining.

Input

The first line contains an integer t(1≤t≤15) — the number of test cases you need to solve.

The first line of each test case contains an integers n(2≤n≤2000) — the number of elements in the array a.

The second line contains n space-separated integers a1, a2, …, an (0≤ai<2^30) — the elements of the array a.

Output

If Baby Ehab can make all elements equal while leaving at least 2

elements standing, print “YES”. Otherwise, print “NO”.

Example

Input

Output

YES
NO

Note

In the first sample, he can remove the first 2 elements, 0 and 2, and replace them by 0⊕2=2. The array will be [2,2], so all the elements are equal.

In the second sample, there’s no way to make all the elements equal.

题意

给一个长度已知的数组，可进行无限次以下操作：

选择数组中两个相邻的数a,b去除，在他们的位置填入一个新数（a^b）。

问给定的数组经过若干次这样的操作后，数组内所有元素能否全部相等？

思路

异或到最后，如果数组满足条件有两种情况

只剩两元素：x,x
只剩三元素：x,x,x

那么就有两种处理：

如果只剩两元素，那么所有元素的累异或就会等于0。
如果只剩三元素，那么情况就会复杂的多。因为最后异或出来的x的值无法确认。所以需要暴力出所有的情况。怎么暴力？，分成三段累异或出来的结果如果相等，则合法。时间复杂度？如果三段全暴力，O(n)为2000*2000*2000，会超限。

简化时间复杂度的两种方法。

法一：原始三段异或的优化。假设全累异或结果为s，第一段为b，第二段为c，则第三段为d = s^b^c。为什么？引理：a^b^b == a。证明：因为s = b^c^d, s^b^c = b^c^d^b^c, b、c消除，则s^b^c = d。（基础：^符号满足结合律和交换律）。这样的话，优化之后的O(n)为2000*2000。不会超限（没有超过1e7）。

法二：定义一个tmp，从0开始异或ai，如果等于所有数的异或结果就清零，再继续，再找到一次等于所有数的异或结果。记录清零的次数，以及最后的结果。根据这两点就可判断是否合法。这样的话，优化之后的O(n)为2000。

法一代码：

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
int n;
int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        cin>>n;
        deque<int> a;
        int num;
        for(int i=0;i<n;i++)
        {
            cin>>num;
            a.push_back(num);
        }

        int s=0;
        for(int i=0;i<n;i++)
        {
            s=s^a[i];
        }
        if(s==0)
        cout<<"YES"<<endl;
        else
        {
            int f=0;
            for(int i=1;i<n-1;i++)
            {
                int b,c,d;
                b=c=d=0;
                for(int ii=0;ii<i;ii++)
                {
                    b^=a[ii];
                }
                for(int j=i+1;j<n;j++)
                {
                    c^=a[j-1];
                    d=s^b^c;
                    if(b==d&&c==d)
                    {
                        f=1;
                        break;
                    }
                }
                if(f) break;
            }
            if(f)
            cout<<"YES"<<endl;
            else
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

法二代码

#include<iostream>
#include<algorithm>
#include<deque>
typedef long long ll;
using namespace std;
int n;
int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        cin>>n;
        deque<ll> a;
        int num;
        for(int i=0;i<n;i++)
        {
            cin>>num;
            a.push_back(num);
        }

        int s=0;
        for(int i=0;i<n;i++)
        {
            s=s^a[i];
        }
        if(s==0){
            cout<<"YES"<<endl;
            continue;
        }
        int tmp = 0;
        int cnt = 0;
        for(int i=0;i<n;i++){
            tmp=tmp^a[i];
            if(tmp == s){
                tmp = 0;
                cnt++;
            }
        }
        if(tmp == 0&&cnt>1)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}