1. 求出 $p_1 \text{ xor } p_i$；
2. 判断 $\sum p_i \text{ and } 2^c$ 是否满足要求，如果不满足，整体 $\text{xor } 2^c$；
3. 整体 $\text{xor mex}(p)$。

这个做法有正确性保证吗？

#include<bits/stdc++.h>
using namespace std;
int a[2000012],q[2000012],s[2400012],b[32];
void in(int x)
{
    for(int i=0;i<=22;i++)
        if(x&(1<<i)) b[i]++;
}
int man()
{
    int n;
    cin>>n;
    memset(b,0,sizeof b);
    in(0);
    for(int i=1;i<=n-1;i++)
        cin>>a[i];
    q[1]=0;
    int cs=0;
    for(int i=1;i<=n-1;i++)
    {
        cs^=a[i];
        q[i+1]=cs;
        in(cs);
    }
    int u=0;
    for(int i=0;i<=22;i++)
    {
        if((n+1)%(1<<i)==0)
        {
            if(b[i]*2==n-1) u+=(1<<i);
        }
        else if(b[i]*2>=n) u+=(1<<i);
    }
    for(int i=1;i<=n;i++)
        q[i]^=u;
    bool ok=false;
    for(int i=1;i<=n;i++)
        if(!q[i]) ok=true;
    for(int i=1;i<=n;i++)
        if(ok) s[q[i]]++;
    int c=1;
    while(s[c]) c++;
    for(int i=1;i<=n;i++)
        s[q[i]]=0;
    for(int i=1;i<=n;i++)
        if(ok) cout<<(q[i]^c)<<' ';
        else cout<<q[i]<<' ';
    cout<<endl;
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--) man();
    return 0;
}