C Beautiful Sequence

题目大意:
$你需要求出字典序第k小的长度为n的单调不降序列A=(A_1,A_2,....,A_n),要求满足:$
$1.对于每一个A_i（1 \le i \le n），0\le A_i \le 2^{30}$
$2.对于每一个1 \le i < n都满足A_i \bigoplus A_{i 1}=B_i,其中B为给定序列，\bigoplus表示按位异或$

$题目分析:$
$首先说明A_1\bigoplus A_i=B_1 \bigoplus B_2.... \bigoplus B_{i-1}$
$证明:$
$由题意得$
$A_1 \bigoplus A_2=B_1$
$A_2 \bigoplus A_3=B_2$
$不妨将两式异或，得A_1 \bigoplus A_2\bigoplus A_2 \bigoplus A_3=B_1 \bigoplus B_2$
$化简为A_1 \bigoplus A_3=B_1 \bigoplus B_2$
$同理归纳可知结论成立$
$所以A_i=B_1 \bigoplus B_2 \bigoplus .....B_{i-1}\bigoplus A_1$
$我们可以记pre_i表示B数组的前缀异或和,那么式子转化为A_i=pre_{i-1} \bigoplus A_1$
$接下来,因为我们已知B序列，即A_i \bigoplus A_{i 1}=B_i,由于A_i \le A_{i 1},因此，在B_i二进制下的最高非零位bit上，A_{i 1}定为1，A_i定为0，才会满足A_i \le A_{i 1}$
$又因A_i=pre_{i-1} \bigoplus A_1,即 A_1=A_i\bigoplus pre_{i-1}$
$所以A_1在bit位上的值便固定了$

$计算每组B_i对A_1产生的固定位(存在矛盾便是无解的)，剩下的位数便是可以随意填的$
$求第k小字典序即为二进制拆分(k-1)，将每一位由低到高填入A_1的非固定位，最后将A_1的二进制形式转化为十进制，求出A_1,再根据A_i=pre_{i-1} \bigoplus A_1求出每一个A_i$

$Tip:注意A_i应小于2^{30}$

参考代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M=1e6+7;

int n,k,T;
LL B[M],pre[M],A[M],c[40];
LL vis[40];
int main(){
	scanf("%d",&T);
	while(T--){
		int f=0;
		scanf("%d%d",&n,&k);
		pre[0]=0;
		for(int i=1;i<n;i++){
			scanf("%lld",&B[i]);
			pre[i]=pre[i-1]^B[i];
		}
		int cnt=31;
		for(int i=0;i<=35;i++) c[i]=vis[i]=0;
	    for(int i=1;i<n;i++){
	    	for(int bit=30;bit>=0;bit--){
	    		if(B[i]==0) continue;
	    	    if((B[i]>>bit)&1){
	    	    	if(pre[i-1]&(1<<bit)){
					    if(vis[bit]&&!c[bit]){
					    	f=1;
					    }
						c[bit]=1; vis[bit]=1;
	    	    	}else {
	    	    		if(vis[bit]&&c[bit]){
					    	f=1;
					    }
						c[bit]=0; vis[bit]=1;
	    	    	}
	    	    	cnt--;
	    	    	break;
	    	    }
	    	}
	    }
        //cout<<f<<" "<<cnt<<"\n";
	    if(f || 1ll*k>(1ll<<cnt)){
	    	printf("-1\n"); continue;
	    } 
	    A[1]=0; cnt=0; k--;
	    while(k){
	    	while(vis[cnt]) cnt++;
	    	if(k&1)  c[cnt]=1;
	    	k>>=1;
	    	cnt++;
	    }
	    for(int bit=0;bit<=30;bit++) A[1]+=(c[bit]<<bit);
	    for(int i=2;i<=n;i++) {
              A[i]=A[1]^pre[i-1];
            if(A[i]>=(1ll<<30)){
                f=1;
            }
        }
        if(f){
            printf("-1\n"); continue;
        }
	    for(int i=1;i<=n;i++)  printf("%lld ",A[i]);
	    printf("\n");
	}	
}