给定 个数 和两个正整数 和 。
将这些数分成恰好 组使得每组的异或和都是 。具体地,每个数都必须出现在恰好一组内。
,。
首先考虑无解情况,显然若 则无解,还有一个不那么显然的是若 中 的最高位为 的数的个数比 小也无解。
接下来考虑构造解,显然由于 且 ,所以只要最大化分的组数就行了。
首先若 则显然 单独分一组最优。
接下来设 的最高位为 ,那么每一组中都至少要有一个数二进制第 位为 ,不妨设二进制第 位为 且不是 的数的集合为 ,那么对于所有 ,都有 ,且对于任意两个不同的 , 和 都不同,所以每个 都可以找到一个唯一对应的数 组成一组 。
这样分组之后显然所有二进制第 位为 的数都单独在一个组,没被分组的数中一定没有二进制第 位为 的了,所以这样分组是最优的,并且剩下的所有数异或起来为 。所以剩下的数可以一起并入任意一组。
设当前分的组数为 ,那么有 ,所以可以不断利用 来合并多余的组,最终一定能得到 组。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
const int S=200005;
int n,k,x;
bool vis[S];
inline void slove()
{
scanf("%d%d%d",&n,&k,&x);
int sum=0;
for(int i=1;i<=n;i++) sum^=i;
if(sum!=(k&1)*x) return puts("NO"),void();
int higbit=-1,tmp=x;
while(tmp>0) tmp>>=1,higbit++;
int cnt=0;
for(int i=1;i<=n;i++) if(i>>higbit&1) cnt++;
if(cnt<k) return puts("NO"),void();
for(int i=1;i<=n;i++) vis[i]=false;
puts("YES");
int tot=0;
if(tot==k-1)
{
cnt=0;
for(int i=1;i<=n;i++) if(!vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i);
printf("\n");
return;
}
if(x<=n) vis[x]=true,printf("1 %d\n",x),tot++;
for(int i=1;i<=n;i++)
{
if(tot==k-1)
{
cnt=0;
for(int i=1;i<=n;i++) if(!vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i);
printf("\n");
return;
}
if(!vis[i]&&(i>>higbit&1))
{
vis[i]=vis[x^i]=true;
printf("2 %d %d\n",i,x^i);
tot++;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T-->0) slove();
return 0;
}