TypeDB Forces 2023 E. The Harmonization of XOR

链接：https://codeforces.com/contest/1787/problem/E
题意：给定n，有一个数组a,满足其所有元素均为1~n，给定k，问能否将数组拆为k个，其每一组的xor为x。
我们发现任意三个xor为k的片段合并后仍为k,我们考虑将序列分为尽量多的xor为k的片段，若tot<k,失败；否则若tot-k为奇数，由总数xor发现不符合条件，失败；否则成功，因为我们可以将多余的（多余的xor一定为0）放入其中一个片段中。
现在问题转化为如何尽量多地划分片段，考虑上界，对于x的二进制最高位，若由s个<=n的数在此位为1，则最多可以分为s个片段。
现证明上界可以取到：对于每个y满足在最高位为1，y xor x < y, 且不同y产生的值两两不同，故可以取到上界。
代码：

#define int long long
using namespace std;

int v[200100],tot;
pair<int,int> c[200100];
void solve(){
	tot=0;
	int sum=0;
	int ans=0;
	int cnt=0;
	int n,k,x;cin>>n>>k>>x;
	for(int i=0;i<=n;i++) v[i]=0;
	for(int i=1;i<=n;i++){
		ans^=i;
		if(v[i]) continue;
		int w=x^i;
		if(w<=n){
			v[i]=1,v[w]=1;
			c[++tot]={i,w};
			ans^=i,ans^=w;
		}
	}
	for(int i=1;i<=n;i++){
		if(!v[i]) sum++;
	}
	if(ans!=0||tot<k||(tot-k)%2){
		puts("NO");
		return;
	}
	puts("YES");
	int p=tot-k;
	for(int i=p+1;i<=tot-1;i++){
		if(c[i].second!=0) cout<<2<<" ";
		else{
		cnt++;
		 cout<<1<<" ";
		 }
		if(c[i].second!=0)
		cout<<c[i].first<<" "<<c[i].second<<" ";
		else cout<<c[i].first<<" ";
		cout<<endl;
	}
		cnt+=2;
		cnt+=sum;
		if(x<=n) cnt--;
		cnt+=p*2;
		cout<<cnt<<" ";
	if(c[tot].second!=0)
	cout<<c[tot].first<<" "<<c[tot].second<<" ";
	else cout<<c[tot].first<<" ";
	for(int i=1;i<=n;i++){
		if(!v[i]){
			cout<<i<<" ";
		}
	}
	if(p){
			for(int i=1;i<=p;i++){
				if(c[i].second!=0)
				cout<<c[i].first<<" "<<c[i].second<<" ";
				else cout<<c[i].first<<" ";
			}
		p=0;
		}
	cout<<endl;
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}