CF1787E The Harmonization of XOR 做题记录

给定 nn 个数 [1,2,3,,n][1,2,3,\ldots,n] 和两个正整数 kkxx

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

1kn21051\le k\le n\le 2\cdot 10^51x1091\le x\le 10^9

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

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

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

接下来设 xx 的最高位为 2k2^k,那么每一组中都至少要有一个数二进制第 kk 位为 11,不妨设二进制第 kk 位为 11 且不是 xx 的数的集合为 SS,那么对于所有 ySy\in S,都有 xy<yx\oplus y<y,且对于任意两个不同的 aS,bSa\in S,b\in Sxax\oplus axbx\oplus b 都不同,所以每个 aSa\in S 都可以找到一个唯一对应的数 b=xab=x\oplus a 组成一组 {a,b}\{a,b\}

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

设当前分的组数为 mm,那么有 mk(mod2)m\equiv k\pmod 2,所以可以不断利用 xxx=xx\oplus x\oplus x=x 来合并多余的组,最终一定能得到 kk 组。

代码如下:

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