题解 | #Random Addition#

c题题解：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+100;

int a[N],b[N],f[N];//f[i]表示从b1到bi的异或和，特殊地，我们规定f[0]=0;
int num[30];//记录a1二进制表示上的各个位数
bool flag;//有没有出现矛盾的标记

int n,k,t;

signed main()
{
    cin>>t;
    while(t--)
    {
        flag=false;//初始化
        cin>>n>>k;
        f[0]=0;
        a[1]=0;
        for(int i=0;i<=29;i++)num[i]=-1;
        for(int i=1;i<=n-1;i++)
        {
            cin>>b[i];
            f[i]=f[i-1]^b[i];//求异或和
        }
        for(int i=0;i<n-1;i++)
        {
            if(flag)break;
            for(int j=29;j>=0;j--)
            {
                if((f[i]>>j&1)!=(f[i+1]>>j&1))//找到了不同位，进行比较
                {
                    if(num[j]==-1)
                    {
                        num[j]=(f[i]>>j&1);
                    }
                    else if(num[j]!=(f[i]>>j&1))
                    {
                        flag=true;//出现了矛盾，标记起来
                    }
                    break;//一但找到不同位，比较完之后直接退出
                }
            }
        }
        if(flag)
        {
            cout<<-1<<endl;
            continue;
        }
        k--;
        int s=0;//方案总数-1
        for(int i=29;i>=0;i--)if(num[i]==-1)s=s*2+1;
        if(s<k)//判断存不存在字典序第k小的方案
        {
            cout<<-1<<endl;
            continue;
        }
        int p=0;
        while(k)//将k拆成二进制，填充到a1的二进制表示中，已经确定的值保持不变
        {
            int x=k&1;
            while(num[p]!=-1)p++;
            num[p]=x;
            k = k >> 1;
        }
        for(int i=0;i<=29;i++)if(num[i]==-1)num[i]=0;//将剩下未填充的数位初始化为0
        for(int i=29;i>=0;i--)a[1]=a[1]*2+num[i];//计算a1,注意从最后一位开始算
        for(int i=2;i<=n;i++)a[i]=a[i-1]^b[i-1];//计算剩下的值
        if(a[n]>=pow(2,30))//判断序列A中是否存在大于等于2^30的数
        {
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        cout<<endl;
    }
}