CF1787E The Harmonization of XOR 做题记录

给定 $n$ 个数 $[1,2,3,\ldots,n]$ 和两个正整数 $k$ 和 $x$。

将这些数分成恰好 $k$ 组使得每组的异或和都是 $x$。具体地，每个数都必须出现在恰好一组内。

$1\le k\le n\le 2\cdot 10^5$，$1\le x\le 10^9$。

首先考虑无解情况，显然若 $1\oplus2\oplus 3\oplus\dots\oplus n\not=[k\operatorname{mod}2=1]x$ 则无解，还有一个不那么显然的是若 $1,2,3,\dots n$ 中 $x$ 的最高位为 $1$ 的数的个数比 $k$ 小也无解。

接下来考虑构造解，显然由于 $x\oplus x\oplus x=x$ 且 $1\oplus2\oplus 3\oplus\dots\oplus n=[k\operatorname{mod}2=1]x$，所以只要最大化分的组数就行了。

首先若 $1\le x\le n$ 则显然 $x$ 单独分一组最优。

接下来设 $x$ 的最高位为 $2^k$，那么每一组中都至少要有一个数二进制第 $k$ 位为 $1$，不妨设二进制第 $k$ 位为 $1$ 且不是 $x$ 的数的集合为 $S$，那么对于所有 $y\in S$，都有 $x\oplus y<y$，且对于任意两个不同的 $a\in S,b\in S$，$x\oplus a$ 和 $x\oplus b$ 都不同，所以每个 $a\in S$ 都可以找到一个唯一对应的数 $b=x\oplus a$ 组成一组 $\{a,b\}$。

这样分组之后显然所有二进制第 $k$ 位为 $1$ 的数都单独在一个组，没被分组的数中一定没有二进制第 $k$ 位为 $1$ 的了，所以这样分组是最优的，并且剩下的所有数异或起来为 $0$。所以剩下的数可以一起并入任意一组。

设当前分的组数为 $m$，那么有 $m\equiv k\pmod 2$，所以可以不断利用 $x\oplus x\oplus x=x$ 来合并多余的组，最终一定能得到 $k$ 组。

代码如下：

#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;
}