[CodeChef XORSACK]Hououin Kyouma and Xorsack

中文版

The problem source is not easy to find, so the problem link is provided.

Definitions:
"A number set" is a set of numbers, "Number sets" means a lot of sets of numbers
"$bit_{i}$" is the $i$-th $bit$ of a number or $\oplus($elements of a number set$)$ ($\oplus$ is the sign of $XOR$)
"$X_{i}$" is number $X$'s $bit_{i}$ ($X$'s $i$-th $bit$)

One $bit$ by one $bit$, we can try maintain the number sets satisfy current conditions.

But the number of number sets is too large ($2^N$)!
What can we do?
It doesn't matter, we can save these $N$ numbers. (call it $s$, $s$ can represent all $2^N$ number sets)
At least later we still can get all the number sets, by enumerate "to choose or not to choose"(call it "choosing state") of each elements of $s$.

The first step is maintain all the number sets, whose $bit_{1}=K_{1}$.

Suppose that $K_{1}=0$
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has even number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=0$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We can prove that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$ (Why? Maybe you could figure out by yourself :))

So, what we should do is replace $s$ with $\{{elements\ (in\ original\ s),\ whose\ bit_{1}=0},s'\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

What if $K_{1}=1$?
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has odd number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=1$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We just know that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$
Why not make each number sets, which originally doesn't contain $v_{1}$, contains $v_{1}$,
and make each number sets, which originally contains $v_{1}$, does not contains $v_{1}$?

Therefore, what should we do was just replace $s$ with $\{\{$elements (in original $s$), whose $bit_{1}=0\},s'$ after modify its $v_{1}$'s choosing state$\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

The problem is, how to modify all number sets' $v_{1}$'s choosing state in $s'$?
We can know that choosing the same number twice, has the effect equals to not to choose the number.
Therefore, we just force it to choose an extra number, $v_{1}$.
For implementation, just let $K\oplus v_{1}$! (But I use another variable, $now$, to represent the changes of $K$)

The answer is $No$ if $v_{1}$ does not exist when we need it.
Or there's nothing going wrong until the last $bit$ is considered (That means there are still number sets satisfy the conditions), the answer is $Yes$

Time complexity: $O(31N)$ (My code enumerates $31$ $bit$s)

code:

#include<cstdio>
#include<cassert>
#include<vector>
using namespace std;
bool Solve(vector<int>s,const int K)
{
    int now=0;
    for(int bit=30;bit>=0;bit--)
    {
        static vector<int>tmp[2];
        for(const int v:s)tmp[(v&(1<<bit))>>bit].push_back(v);
        s.swap(tmp[0]);
        if((now^K)&(1<<bit))
        {
            if(tmp[1].empty())return false;
            now^=tmp[1][0];
        }
        for(int i=1;i<(int)tmp[1].size();i++)s.push_back(tmp[1][i-1]^tmp[1][i]);
        for(int d=0;d<2;d++)vector<int>().swap(tmp[d]);
    }
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int N,K;
    scanf("%d%d",&N,&K);
    vector<int>s;
    for(int i=0,v;i<N;i++)scanf("%d",&v),s.push_back(v);
    puts(Solve(s,K)?"Yes":"No");
    return 0;
}